diff options
| author | Jabier Arraiza <jabier.arraiza@marker.es> | 2017-07-01 23:31:49 +0000 |
|---|---|---|
| committer | Jabier Arraiza <jabier.arraiza@marker.es> | 2017-07-01 23:31:49 +0000 |
| commit | 03bb87a0175289274132a0240628936fbccf6ca5 (patch) | |
| tree | 979519e873c0ceff7a6a8b0f53252a4a5ece1143 /src/libvpsc | |
| parent | Improving CR feedback. thanks! (diff) | |
| parent | When running without installing, extensions will spawn correct Inkscape (diff) | |
| download | inkscape-03bb87a0175289274132a0240628936fbccf6ca5.tar.gz inkscape-03bb87a0175289274132a0240628936fbccf6ca5.zip | |
Merge https://gitlab.com/inkscape/inkscape into selectable-knots
Diffstat (limited to 'src/libvpsc')
36 files changed, 5468 insertions, 2145 deletions
diff --git a/src/libvpsc/CMakeLists.txt b/src/libvpsc/CMakeLists.txt index aa693670c..60fed84ea 100644 --- a/src/libvpsc/CMakeLists.txt +++ b/src/libvpsc/CMakeLists.txt @@ -2,24 +2,25 @@ set(libvpsc_SRC block.cpp blocks.cpp + cbuffer.cpp constraint.cpp - generate-constraints.cpp - remove_rectangle_overlap.cpp + rectangle.cpp solve_VPSC.cpp variable.cpp - pairingheap/PairingHeap.cpp # ------- # Headers + assertions.h block.h blocks.h + cbuffer.h constraint.h - generate-constraints.h - pairingheap/PairingHeap.h - pairingheap/dsexceptions.h - placement_SolveVPSC.h - remove_rectangle_overlap.h + exceptions.h + isnan.h + linesegment.h + pairing_heap.h + rectangle.h solve_VPSC.h variable.h ) diff --git a/src/libvpsc/Makefile.am b/src/libvpsc/Makefile.am new file mode 100644 index 000000000..12e779aa8 --- /dev/null +++ b/src/libvpsc/Makefile.am @@ -0,0 +1,42 @@ +EXTRA_DIST=libvpsc.pc.in +lib_LTLIBRARIES = libvpsc.la +libvpsc_la_CPPFLAGS = -I$(top_srcdir) -I$(includedir)/libvpsc -fPIC +libvpsc_la_LDFLAGS = -no-undefined + +#DEFS=-DLIBVPSC_LOGGING + + +libvpsc_la_SOURCES = block.cpp\ + blocks.cpp\ + constraint.cpp\ + rectangle.cpp\ + solve_VPSC.cpp\ + variable.cpp\ + cbuffer.cpp\ + isnan.h\ + block.h\ + blocks.h\ + constraint.h\ + rectangle.h\ + pairingheap.h\ + solve_VPSC.h\ + variable.h\ + cbuffer.h\ + linesegment.h\ + assertions.h + +libvpscincludedir = $(includedir)/libvpsc + +libvpscinclude_HEADERS = solve_VPSC.h \ + block.h\ + constraint.h\ + exceptions.h\ + rectangle.h\ + variable.h \ + assertions.h + +pkgconfigdir = $(libdir)/pkgconfig +pkgconfig_DATA = libvpsc.pc + +SUBDIRS = . tests + diff --git a/src/libvpsc/assertions.h b/src/libvpsc/assertions.h new file mode 100644 index 000000000..68eab8f11 --- /dev/null +++ b/src/libvpsc/assertions.h @@ -0,0 +1,102 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. + * + * Copyright (C) 2009 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. + * +*/ + +#ifndef VPSC_ASSERTIONS_H +#define VPSC_ASSERTIONS_H + +#ifdef NDEBUG + + #define COLA_ASSERT(expr) static_cast<void>(0) + +#else // Not NDEBUG + + // sstream needs ::strcpy_s under MinGW so include cstring. + #include <cstring> + + #include <sstream> + #include <cassert> + + #if defined(USE_ASSERT_EXCEPTIONS) + + // String seems to be missing on MinGW's gcc, + // so define it here if it is missing. + #ifndef __STRING + #define __STRING(x) #x + #endif + + #if !defined(__ASSERT_FUNCTION) + #define COLA_ASSERT(expr) \ + if (!(expr)) { \ + throw vpsc::CriticalFailure(__STRING(expr), __FILE__, __LINE__); \ + } + #else + #define COLA_ASSERT(expr) \ + if (!(expr)) { \ + throw vpsc::CriticalFailure(__STRING(expr), __FILE__, __LINE__, \ + __ASSERT_FUNCTION); \ + } + #endif + + #else + #define COLA_ASSERT(expr) assert(expr) + #endif + +namespace vpsc { + +// Critical failure: either something went wrong, or (more likely) there +// was infeasible input. +class CriticalFailure +{ + public: + CriticalFailure(const char *expr, const char *file, int line, + const char *function = NULL) + : expr(expr), + file(file), + line(line), + function(function) + { + } + std::string what() const + { + std::stringstream s; + s << "ERROR: Critical assertion failed.\n"; + s << " expression: " << expr << "\n"; + s << " at line " << line << " of " << file << "\n"; + if (function) + { + s << " in: " << function << "\n"; + } + + return s.str(); + } + private: + const char *expr; + const char *file; + int line; + const char *function; +}; + +} + +#endif // NDEBUG + + +#endif // VPSC_ASSERTIONS_H + diff --git a/src/libvpsc/block.cpp b/src/libvpsc/block.cpp index 8171780d4..a5e7ed0d1 100644 --- a/src/libvpsc/block.cpp +++ b/src/libvpsc/block.cpp @@ -1,208 +1,292 @@ /* - * Authors: - * Tim Dwyer <tgdwyer@gmail.com> + * vim: ts=4 sw=4 et tw=0 wm=0 * - * Copyright (C) 2005 Authors + * 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 +*/ + +/* + * @brief A block is a group of variables that must be moved together to improve + * the goal function without violating already active constraints. + * The variables in a block are spanned by a tree of active constraints. * - * Released under GNU LGPL. Read the file 'COPYING' for more information. */ + +#include "libvpsc/block.h" +#include "libvpsc/variable.h" #include <cassert> -#include "pairingheap/PairingHeap.h" -#include "constraint.h" -#include "block.h" -#include "blocks.h" -#ifdef RECTANGLE_OVERLAP_LOGGING +#include "libvpsc/pairing_heap.h" +#include "libvpsc/constraint.h" +#include "libvpsc/exceptions.h" +#include "libvpsc/blocks.h" + +#ifdef LIBVPSC_LOGGING #include <fstream> using std::ios; using std::ofstream; using std::endl; #endif -using std::vector; + +#define __NOTNAN(p) (p)==(p) namespace vpsc { -void Block::addVariable(Variable* const v) { - v->block=this; - vars->push_back(v); - weight+=v->weight; - wposn += v->weight * (v->desiredPosition - v->offset); - posn=wposn/weight; -} -Block::Block(Variable* const v) { - timeStamp=0; - posn=weight=wposn=0; - in=NULL; - out=NULL; - deleted=false; - vars=new vector<Variable*>; - if(v!=NULL) { - v->offset=0; - addVariable(v); - } +void PositionStats::addVariable(Variable* v) { + double ai=scale/v->scale; + double bi=v->offset/v->scale; + double wi=v->weight; + AB+=wi*ai*bi; + AD+=wi*ai*v->desiredPosition; + A2+=wi*ai*ai; + /* +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f << "adding v[" << v->id << "], blockscale=" << scale << ", despos=" + << v->desiredPosition << ", ai=" << ai << ", bi=" << bi + << ", AB=" << AB << ", AD=" << AD << ", A2=" << A2; +#endif +*/ +} +void Block::addVariable(Variable* v) { + v->block=this; + vars->push_back(v); + if(ps.A2==0) ps.scale=v->scale; + //weight+= v->weight; + //wposn += v->weight * (v->desiredPosition - v->offset); + //posn=wposn/weight; + ps.addVariable(v); + posn=(ps.AD - ps.AB) / ps.A2; + COLA_ASSERT(__NOTNAN(posn)); + /* +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f << ", posn=" << posn << endl; +#endif +*/ +} +Block::Block(Blocks *blocks, Variable* const v) + : vars(new std::vector<Variable*>) + , posn(0) + //, weight(0) + //, wposn(0) + , deleted(false) + , timeStamp(0) + , in(NULL) + , out(NULL) + , blocks(blocks) +{ + if(v!=NULL) { + v->offset=0; + addVariable(v); + } } -double Block::desiredWeightedPosition() { - double wp = 0; - for (Vit v=vars->begin();v!=vars->end();++v) { - wp += ((*v)->desiredPosition - (*v)->offset) * (*v)->weight; - } - return wp; +void Block::updateWeightedPosition() { + //wposn=0; + ps.AB=ps.AD=ps.A2=0; + for (Vit v=vars->begin();v!=vars->end();++v) { + //wposn += ((*v)->desiredPosition - (*v)->offset) * (*v)->weight; + ps.addVariable(*v); + } + posn=(ps.AD - ps.AB) / ps.A2; + COLA_ASSERT(__NOTNAN(posn)); +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f << ", posn=" << posn << endl; +#endif } Block::~Block(void) { - delete vars; - delete in; - delete out; + delete vars; + delete in; + delete out; } void Block::setUpInConstraints() { - setUpConstraintHeap(in,true); + setUpConstraintHeap(in,true); } void Block::setUpOutConstraints() { - setUpConstraintHeap(out,false); -} -void Block::setUpConstraintHeap(PairingHeap<Constraint*>* &h,bool in) { - delete h; - h = new PairingHeap<Constraint*>(&compareConstraints); - for (Vit i=vars->begin();i!=vars->end();++i) { - Variable *v=*i; - vector<Constraint*> *cs=in?&(v->in):&(v->out); - for (Cit j=cs->begin();j!=cs->end();++j) { - Constraint *c=*j; - c->timeStamp=blockTimeCtr; - if ((c->left->block != this && in) || (c->right->block != this && !in)) { - h->insert(c); - } - } - } -} -void Block::merge(Block* b, Constraint* c) { -#ifdef RECTANGLE_OVERLAP_LOGGING - ofstream f(LOGFILE,ios::app); - f<<" merging on: "<<*c<<",c->left->offset="<<c->left->offset<<",c->right->offset="<<c->right->offset<<endl; + setUpConstraintHeap(out,false); +} +void Block::setUpConstraintHeap(PairingHeap<Constraint*,CompareConstraints>* &h,bool in) { + delete h; + h = new PairingHeap<Constraint*,CompareConstraints>(); + for (Vit i=vars->begin();i!=vars->end();++i) { + Variable *v=*i; + std::vector<Constraint*> *cs=in?&(v->in):&(v->out); + for (Cit j=cs->begin();j!=cs->end();++j) { + Constraint *c=*j; + c->timeStamp=blocks->blockTimeCtr; + if ( ((c->left->block != this) && in) || + ((c->right->block != this) && !in) ) + { + h->insert(c); + } + } + } +} +Block* Block::merge(Block* b, Constraint* c) { +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<" merging on: "<<*c<<",c->left->offset="<<c->left->offset<<",c->right->offset="<<c->right->offset<<endl; #endif - double dist = c->right->offset - c->left->offset - c->gap; - Block *l=c->left->block; - Block *r=c->right->block; - if (vars->size() < b->vars->size()) { - r->merge(l,c,dist); - } else { - l->merge(r,c,-dist); - } -#ifdef RECTANGLE_OVERLAP_LOGGING - f<<" merged block="<<(b->deleted?*this:*b)<<endl; + double dist = c->right->offset - c->left->offset - c->gap; + Block *l=c->left->block; + Block *r=c->right->block; + if (l->vars->size() < r->vars->size()) { + r->merge(l,c,dist); + } else { + l->merge(r,c,-dist); + } + Block* mergeBlock=b->deleted?this:b; +#ifdef LIBVPSC_LOGGING + f<<" merged block="<<*mergeBlock<<endl; #endif + return mergeBlock; } - +/* + * Merges b into this block across c. Can be either a + * right merge or a left merge + * @param b block to merge into this + * @param c constraint being merged + * @param distance separation required to satisfy c + */ void Block::merge(Block *b, Constraint *c, double dist) { -#ifdef RECTANGLE_OVERLAP_LOGGING - ofstream f(LOGFILE,ios::app); - f<<" merging: "<<*b<<"dist="<<dist<<endl; +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<" merging: "<<*b<<"dist="<<dist<<endl; #endif - c->active=true; - wposn+=b->wposn-dist*b->weight; - weight+=b->weight; - posn=wposn/weight; - for(Vit i=b->vars->begin();i!=b->vars->end();++i) { - Variable *v=*i; - v->block=this; - v->offset+=dist; - vars->push_back(v); - } - b->deleted=true; + c->active=true; + //wposn+=b->wposn-dist*b->weight; + //weight+=b->weight; + for(Vit i=b->vars->begin();i!=b->vars->end();++i) { + Variable *v=*i; + //v->block=this; + //vars->push_back(v); + v->offset+=dist; + addVariable(v); + } +#ifdef LIBVPSC_LOGGING + for(Vit i=vars->begin();i!=vars->end();++i) { + Variable *v=*i; + f<<" v["<<v->id<<"]: d="<<v->desiredPosition + <<" a="<<v->scale<<" o="<<v->offset + <<endl; + } + f<<" AD="<<ps.AD<<" AB="<<ps.AB<<" A2="<<ps.A2<<endl; +#endif + //posn=wposn/weight; + //COLA_ASSERT(wposn==ps.AD - ps.AB); + posn=(ps.AD - ps.AB) / ps.A2; + COLA_ASSERT(__NOTNAN(posn)); + b->deleted=true; } void Block::mergeIn(Block *b) { -#ifdef RECTANGLE_OVERLAP_LOGGING - ofstream f(LOGFILE,ios::app); - f<<" merging constraint heaps... "<<endl; +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<" merging constraint heaps... "<<endl; #endif - // We check the top of the heaps to remove possible internal constraints - findMinInConstraint(); - b->findMinInConstraint(); - in->merge(b->in); -#ifdef RECTANGLE_OVERLAP_LOGGING - f<<" merged heap: "<<*in<<endl; + // We check the top of the heaps to remove possible internal constraints + findMinInConstraint(); + b->findMinInConstraint(); + in->merge(b->in); +#ifdef LIBVPSC_LOGGING + f<<" merged heap: "<<*in<<endl; #endif } -void Block::mergeOut(Block *b) { - findMinOutConstraint(); - b->findMinOutConstraint(); - out->merge(b->out); +void Block::mergeOut(Block *b) { + findMinOutConstraint(); + b->findMinOutConstraint(); + out->merge(b->out); } Constraint *Block::findMinInConstraint() { - Constraint *v = NULL; - vector<Constraint*> outOfDate; - while (!in->isEmpty()) { - v = in->findMin(); - Block *lb=v->left->block; - Block *rb=v->right->block; - // rb may not be this if called between merge and mergeIn -#ifdef RECTANGLE_OVERLAP_LOGGING - ofstream f(LOGFILE,ios::app); - f<<" checking constraint ... "<<*v; - f<<" timestamps: left="<<lb->timeStamp<<" right="<<rb->timeStamp<<" constraint="<<v->timeStamp<<endl; + Constraint *v = NULL; + std::vector<Constraint*> outOfDate; + while (!in->isEmpty()) { + v = in->findMin(); + Block *lb=v->left->block; + Block *rb=v->right->block; + // rb may not be this if called between merge and mergeIn +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<" checking constraint ... "<<*v; + f<<" timestamps: left="<<lb->timeStamp<<" right="<<rb->timeStamp<<" constraint="<<v->timeStamp<<endl; #endif - if(lb == rb) { - // constraint has been merged into the same block -#ifdef RECTANGLE_OVERLAP_LOGGING - if(v->slack()<0) { - f<<" violated internal constraint found! "<<*v<<endl; - f<<" lb="<<*lb<<endl; - f<<" rb="<<*rb<<endl; - } + if(lb == rb) { + // constraint has been merged into the same block +#ifdef LIBVPSC_LOGGING + if(v->slack()<0) { + f<<" violated internal constraint found! "<<*v<<endl; + f<<" lb="<<*lb<<endl; + f<<" rb="<<*rb<<endl; + } #endif - in->deleteMin(); -#ifdef RECTANGLE_OVERLAP_LOGGING - f<<" ... skipping internal constraint"<<endl; + in->deleteMin(); +#ifdef LIBVPSC_LOGGING + f<<" ... skipping internal constraint"<<endl; #endif - } else if(v->timeStamp < lb->timeStamp) { - // block at other end of constraint has been moved since this - in->deleteMin(); - outOfDate.push_back(v); -#ifdef RECTANGLE_OVERLAP_LOGGING - f<<" reinserting out of date (reinsert later)"<<endl; + } else if(v->timeStamp < lb->timeStamp) { + // block at other end of constraint has been moved since this + in->deleteMin(); + outOfDate.push_back(v); +#ifdef LIBVPSC_LOGGING + f<<" reinserting out of date (reinsert later)"<<endl; #endif - } else { - break; - } - } - for(Cit i=outOfDate.begin();i!=outOfDate.end();++i) { - v=*i; - v->timeStamp=blockTimeCtr; - in->insert(v); - } - if(in->isEmpty()) { - v=NULL; - } else { - v=in->findMin(); - } - return v; + } else { + break; + } + } + for(Cit i=outOfDate.begin();i!=outOfDate.end();++i) { + v=*i; + v->timeStamp=blocks->blockTimeCtr; + in->insert(v); + } + if(in->isEmpty()) { + v=NULL; + } else { + v=in->findMin(); + } + return v; } Constraint *Block::findMinOutConstraint() { - if(out->isEmpty()) return NULL; - Constraint *v = out->findMin(); - while (v->left->block == v->right->block) { - out->deleteMin(); - if(out->isEmpty()) return NULL; - v = out->findMin(); - } - return v; + if(out->isEmpty()) return NULL; + Constraint *v = out->findMin(); + while (v->left->block == v->right->block) { + out->deleteMin(); + if(out->isEmpty()) return NULL; + v = out->findMin(); + } + return v; } void Block::deleteMinInConstraint() { - in->deleteMin(); -#ifdef RECTANGLE_OVERLAP_LOGGING - ofstream f(LOGFILE,ios::app); - f<<"deleteMinInConstraint... "<<endl; - f<<" result: "<<*in<<endl; + in->deleteMin(); +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"deleteMinInConstraint... "<<endl; + f<<" result: "<<*in<<endl; #endif } void Block::deleteMinOutConstraint() { - out->deleteMin(); + out->deleteMin(); } -inline bool Block::canFollowLeft(Constraint *c, const Variable* const last) { - return c->left->block==this && c->active && last!=c->left; +inline bool Block::canFollowLeft(Constraint const* c, Variable const* last) const { + return c->left->block==this && c->active && last!=c->left; } -inline bool Block::canFollowRight(Constraint *c, const Variable* const last) { - return c->right->block==this && c->active && last!=c->right; +inline bool Block::canFollowRight(Constraint const* c, Variable const* last) const { + return c->right->block==this && c->active && last!=c->right; } // computes the derivative of v and the lagrange multipliers @@ -211,32 +295,47 @@ inline bool Block::canFollowRight(Constraint *c, const Variable* const last) { // also records the constraint with minimum lagrange multiplier // in min_lm double Block::compute_dfdv(Variable* const v, Variable* const u, - Constraint *&min_lm) { - double dfdv=v->weight*(v->position() - v->desiredPosition); - for(Cit it=v->out.begin();it!=v->out.end();++it) { - Constraint *c=*it; - if(canFollowRight(c,u)) { - dfdv+=c->lm=compute_dfdv(c->right,v,min_lm); - if(!c->equality&&(min_lm==NULL||c->lm<min_lm->lm)) min_lm=c; - } - } - for(Cit it=v->in.begin();it!=v->in.end();++it) { - Constraint *c=*it; - if(canFollowLeft(c,u)) { - dfdv-=c->lm=-compute_dfdv(c->left,v,min_lm); - if(!c->equality&&(min_lm==NULL||c->lm<min_lm->lm)) min_lm=c; - } - } - return dfdv; + Constraint *&min_lm) { + double dfdv=v->dfdv(); + for(Cit it=v->out.begin();it!=v->out.end();++it) { + Constraint *c=*it; + if(canFollowRight(c,u)) { + c->lm=compute_dfdv(c->right,v,min_lm); + dfdv+=c->lm*c->left->scale; + if(!c->equality&&(min_lm==NULL||c->lm<min_lm->lm)) min_lm=c; + } + } + for(Cit it=v->in.begin();it!=v->in.end();++it) { + Constraint *c=*it; + if(canFollowLeft(c,u)) { + c->lm=-compute_dfdv(c->left,v,min_lm); + dfdv-=c->lm*c->right->scale; + if(!c->equality&&(min_lm==NULL||c->lm<min_lm->lm)) min_lm=c; + } + } + return dfdv/v->scale; +} +double Block::compute_dfdv(Variable* const v, Variable* const u) { + double dfdv = v->dfdv(); + for(Cit it = v->out.begin(); it != v->out.end(); ++it) { + Constraint *c = *it; + if(canFollowRight(c,u)) { + c->lm = compute_dfdv(c->right,v); + dfdv += c->lm * c->left->scale; + } + } + for(Cit it=v->in.begin();it!=v->in.end();++it) { + Constraint *c = *it; + if(canFollowLeft(c,u)) { + c->lm = - compute_dfdv(c->left,v); + dfdv -= c->lm * c->right->scale; + } + } + return dfdv/v->scale; } - -// computes dfdv for each variable and uses the sum of dfdv on either side of -// the constraint c to compute the lagrangian multiplier lm_c. // The top level v and r are variables between which we want to find the // constraint with the smallest lm. -// When we find r we pass NULL to subsequent recursive calls, -// thus r=NULL indicates constraints are not on the shortest path. // Similarly, m is initially NULL and is only assigned a value if the next // variable to be visited is r or if a possible min constraint is returned from // a nested call (rather than NULL). @@ -244,153 +343,305 @@ double Block::compute_dfdv(Variable* const v, Variable* const u, // the recursion (checking only constraints traversed left-to-right // in order to avoid creating any new violations). // We also do not consider equality constraints as potential split points +bool Block::split_path( + Variable* r, + Variable* const v, + Variable* const u, + Constraint* &m, + bool desperation=false + ) +{ + for(Cit it(v->in.begin());it!=v->in.end();++it) { + Constraint *c=*it; + if(canFollowLeft(c,u)) { +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<" left split path: "<<*c<<endl; +#endif + if(c->left==r) { + if(desperation&&!c->equality) m=c; + return true; + } else { + if(split_path(r,c->left,v,m)) { + if(desperation && !c->equality && (!m||c->lm<m->lm)) { + m=c; + } + return true; + } + } + } + } + for(Cit it(v->out.begin());it!=v->out.end();++it) { + Constraint *c=*it; + if(canFollowRight(c,u)) { +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<" right split path: "<<*c<<endl; +#endif + if(c->right==r) { + if(!c->equality) m=c; + return true; + } else { + if(split_path(r,c->right,v,m)) { + if(!c->equality && (!m||c->lm<m->lm)) + m=c; + return true; + } + } + } + } + return false; +} +/* Block::Pair Block::compute_dfdv_between( - Variable* r, Variable* const v, Variable* const u, - const Direction dir = NONE, bool changedDirection = false) { - double dfdv=v->weight*(v->position() - v->desiredPosition); - Constraint *m=NULL; - for(Cit it(v->in.begin());it!=v->in.end();++it) { - Constraint *c=*it; - if(canFollowLeft(c,u)) { - if(dir==RIGHT) { - changedDirection = true; - } - if(c->left==r) { - r=NULL; - if(!c->equality) m=c; - } - Pair p=compute_dfdv_between(r,c->left,v, - LEFT,changedDirection); - dfdv -= c->lm = -p.first; - if(r && p.second) - m = p.second; - } - } - for(Cit it(v->out.begin());it!=v->out.end();++it) { - Constraint *c=*it; - if(canFollowRight(c,u)) { - if(dir==LEFT) { - changedDirection = true; - } - if(c->right==r) { - r=NULL; - if(!c->equality) m=c; - } - Pair p=compute_dfdv_between(r,c->right,v, - RIGHT,changedDirection); - dfdv += c->lm = p.first; - if(r && p.second) - m = changedDirection && !c->equality && c->lm < p.second->lm - ? c - : p.second; - } - } - return Pair(dfdv,m); + Variable* r, Variable* const v, Variable* const u, + const Direction dir = NONE, bool changedDirection = false) { + double dfdv=v->weight*(v->position() - v->desiredPosition); + Constraint *m=NULL; + for(Cit it(v->in.begin());it!=v->in.end();++it) { + Constraint *c=*it; + if(canFollowLeft(c,u)) { + if(dir==RIGHT) { + changedDirection = true; + } + if(c->left==r) { + r=NULL; + if(!c->equality) m=c; + } + Pair p=compute_dfdv_between(r,c->left,v, + LEFT,changedDirection); + dfdv -= c->lm = -p.first; + if(r && p.second) + m = p.second; + } + } + for(Cit it(v->out.begin());it!=v->out.end();++it) { + Constraint *c=*it; + if(canFollowRight(c,u)) { + if(dir==LEFT) { + changedDirection = true; + } + if(c->right==r) { + r=NULL; + if(!c->equality) m=c; + } + Pair p=compute_dfdv_between(r,c->right,v, + RIGHT,changedDirection); + dfdv += c->lm = p.first; + if(r && p.second) + m = changedDirection && !c->equality && c->lm < p.second->lm + ? c + : p.second; + } + } + return Pair(dfdv,m); } +*/ // resets LMs for all active constraints to 0 by // traversing active constraint tree starting from v, // not back tracking over u void Block::reset_active_lm(Variable* const v, Variable* const u) { - for(Cit it=v->out.begin();it!=v->out.end();++it) { - Constraint *c=*it; - if(canFollowRight(c,u)) { - c->lm=0; - reset_active_lm(c->right,v); - } - } - for(Cit it=v->in.begin();it!=v->in.end();++it) { - Constraint *c=*it; - if(canFollowLeft(c,u)) { - c->lm=0; - reset_active_lm(c->left,v); - } - } + for(Cit it=v->out.begin();it!=v->out.end();++it) { + Constraint *c=*it; + if(canFollowRight(c,u)) { + c->lm=0; + reset_active_lm(c->right,v); + } + } + for(Cit it=v->in.begin();it!=v->in.end();++it) { + Constraint *c=*it; + if(canFollowLeft(c,u)) { + c->lm=0; + reset_active_lm(c->left,v); + } + } } - +void Block::list_active(Variable* const v, Variable* const u) { + for(Cit it=v->out.begin();it!=v->out.end();++it) { + Constraint *c=*it; + if(canFollowRight(c,u)) { +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<" "<<*c<<endl; +#endif + list_active(c->right,v); + } + } + for(Cit it=v->in.begin();it!=v->in.end();++it) { + Constraint *c=*it; + if(canFollowLeft(c,u)) { +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<" "<<*c<<endl; +#endif + list_active(c->left,v); + } + } +} +/* + * finds the constraint with the minimum lagrange multiplier, that is, the constraint + * that most wants to split + */ Constraint *Block::findMinLM() { - Constraint *min_lm=NULL; - reset_active_lm(vars->front(),NULL); - compute_dfdv(vars->front(),NULL,min_lm); - return min_lm; + Constraint *min_lm=NULL; + reset_active_lm(vars->front(),NULL); + compute_dfdv(vars->front(),NULL,min_lm); +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<" langrangians: "<<endl; + list_active(vars->front(),NULL); +#endif + return min_lm; } Constraint *Block::findMinLMBetween(Variable* const lv, Variable* const rv) { - Constraint *min_lm=NULL; - reset_active_lm(vars->front(),NULL); - min_lm=compute_dfdv_between(rv,lv,NULL).second; - return min_lm; + reset_active_lm(vars->front(),NULL); + compute_dfdv(vars->front(),NULL); + Constraint *min_lm=NULL; + split_path(rv,lv,NULL,min_lm); +#if 0 + if(min_lm==NULL) { + split_path(rv,lv,NULL,min_lm,true); + } +#else + if(min_lm==NULL) { +#ifdef LIBVPSC_DEBUG + fprintf(stderr,"Couldn't find split point!\n"); +#endif + UnsatisfiableException e; + getActivePathBetween(e.path,lv,rv,NULL); + throw e; + } + COLA_ASSERT(min_lm!=NULL); +#endif + return min_lm; } // populates block b by traversing the active constraint tree adding variables as they're // visited. Starts from variable v and does not backtrack over variable u. -void Block::populateSplitBlock(Block *b, Variable* const v, Variable* const u) { - b->addVariable(v); - for (Cit c=v->in.begin();c!=v->in.end();++c) { - if (canFollowLeft(*c,u)) - populateSplitBlock(b, (*c)->left, v); - } - for (Cit c=v->out.begin();c!=v->out.end();++c) { - if (canFollowRight(*c,u)) - populateSplitBlock(b, (*c)->right, v); - } +void Block::populateSplitBlock(Block *b, Variable* v, Variable const* u) { + b->addVariable(v); + for (Cit c=v->in.begin();c!=v->in.end();++c) { + if (canFollowLeft(*c,u)) + populateSplitBlock(b, (*c)->left, v); + } + for (Cit c=v->out.begin();c!=v->out.end();++c) { + if (canFollowRight(*c,u)) + populateSplitBlock(b, (*c)->right, v); + } +} +/* + * Returns the active path between variables u and v... not back tracking over w + */ +bool Block::getActivePathBetween(Constraints& path, Variable const* u, + Variable const* v, Variable const *w) const { + if(u==v) return true; + for (Cit_const c=u->in.begin();c!=u->in.end();++c) { + if (canFollowLeft(*c,w)) { + if(getActivePathBetween(path, (*c)->left, v, u)) { + path.push_back(*c); + return true; + } + } + } + for (Cit_const c=u->out.begin();c!=u->out.end();++c) { + if (canFollowRight(*c,w)) { + if(getActivePathBetween(path, (*c)->right, v, u)) { + path.push_back(*c); + return true; + } + } + } + return false; } // Search active constraint tree from u to see if there is a directed path to v. // Returns true if path is found with all constraints in path having their visited flag // set true. -bool Block::isActiveDirectedPathBetween(Variable* u, Variable *v) { - if(u==v) return true; - for (Cit c=u->out.begin();c!=u->out.end();++c) { - if(canFollowRight(*c,NULL)) { - if(isActiveDirectedPathBetween((*c)->right,v)) { - (*c)->visited=true; - return true; - } - (*c)->visited=false; - } - } - return false; +bool Block::isActiveDirectedPathBetween(Variable const* u, Variable const* v) const { + if(u==v) return true; + for (Cit_const c=u->out.begin();c!=u->out.end();++c) { + if(canFollowRight(*c,NULL)) { + if(isActiveDirectedPathBetween((*c)->right,v)) { + return true; + } + } + } + return false; } - +bool Block::getActiveDirectedPathBetween( + Constraints& path, Variable const* u, Variable const* v) const { + if(u==v) return true; + for (Cit_const c=u->out.begin();c!=u->out.end();++c) { + if(canFollowRight(*c,NULL)) { + if(getActiveDirectedPathBetween(path,(*c)->right,v)) { + path.push_back(*c); + return true; + } + } + } + return false; +} +/* + * Block needs to be split because of a violated constraint between vl and vr. + * We need to search the active constraint tree between l and r and find the constraint + * with min lagrangrian multiplier and split at that point. + * Returns the split constraint + */ Constraint* Block::splitBetween(Variable* const vl, Variable* const vr, - Block* &lb, Block* &rb) { -#ifdef RECTANGLE_OVERLAP_LOGGING - ofstream f(LOGFILE,ios::app); - f<<" need to split between: "<<*vl<<" and "<<*vr<<endl; + Block* &lb, Block* &rb) { +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<" need to split between: "<<*vl<<" and "<<*vr<<endl; #endif - Constraint *c=findMinLMBetween(vl, vr); -#ifdef RECTANGLE_OVERLAP_LOGGING - f<<" going to split on: "<<*c<<endl; + Constraint *c=findMinLMBetween(vl, vr); +#ifdef LIBVPSC_LOGGING + f<<" going to split on: "<<*c<<endl; #endif - split(lb,rb,c); - deleted = true; - return c; + if(c!=NULL) { + split(lb,rb,c); + deleted = true; + } + return c; } +/* + * Creates two new blocks, l and r, and splits this block across constraint c, + * placing the left subtree of constraints (and associated variables) into l + * and the right into r. + */ void Block::split(Block* &l, Block* &r, Constraint* c) { - c->active=false; - l=new Block(); - populateSplitBlock(l,c->left,c->right); - r=new Block(); - populateSplitBlock(r,c->right,c->left); + c->active=false; + l=new Block(blocks); + populateSplitBlock(l,c->left,c->right); + //COLA_ASSERT(l->weight>0); + r=new Block(blocks); + populateSplitBlock(r,c->right,c->left); + //COLA_ASSERT(r->weight>0); } +/* + * Computes the cost (squared euclidean distance from desired positions) of the + * current positions for variables in this block + */ double Block::cost() { - double c = 0; - for (Vit v=vars->begin();v!=vars->end();++v) { - double diff = (*v)->position() - (*v)->desiredPosition; - c += (*v)->weight * diff * diff; - } - return c; -} -ostream& operator <<(ostream &os, const Block& b) + double c = 0; + for (Vit v=vars->begin();v!=vars->end();++v) { + double diff = (*v)->position() - (*v)->desiredPosition; + c += (*v)->weight * diff * diff; + } + return c; +} +std::ostream& operator <<(std::ostream &os, const Block& b) { - os<<"Block:"; - for(Block::Vit v=b.vars->begin();v!=b.vars->end();++v) { - os<<" "<<**v; - } - if(b.deleted) { - os<<" Deleted!"; - } + os<<"Block(posn="<<b.posn<<"):"; + for(Block::Vit v=b.vars->begin();v!=b.vars->end();++v) { + os<<" "<<**v; + } + if(b.deleted) { + os<<" Deleted!"; + } return os; } + } + diff --git a/src/libvpsc/block.h b/src/libvpsc/block.h index 9c90fc87e..21a3737b7 100644 --- a/src/libvpsc/block.h +++ b/src/libvpsc/block.h @@ -1,122 +1,113 @@ /* - * Authors: - * Tim Dwyer <tgdwyer@gmail.com> + * vim: ts=4 sw=4 et tw=0 wm=0 * - * Copyright (C) 2005 Authors + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. * - * Released under GNU LGPL. Read the file 'COPYING' for more information. + * 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 +*/ + +/* + * \brief A block is a group of variables that must be moved together to improve + * the goal function without violating already active constraints. + * The variables in a block are spanned by a tree of active constraints. */ -#ifndef SEEN_REMOVEOVERLAP_BLOCK_H -#define SEEN_REMOVEOVERLAP_BLOCK_H +#ifndef VPSC_BLOCK_H +#define VPSC_BLOCK_H -#include <vector> #include <iostream> -template <class T> class PairingHeap; +#include <vector> + +template <class T, class TCompare> class PairingHeap; + namespace vpsc { class Variable; class Constraint; +class CompareConstraints; +class Blocks; + +struct PositionStats { + PositionStats() : scale(0), AB(0), AD(0), A2(0) {} + void addVariable(Variable* const v); + double scale; + double AB; + double AD; + double A2; +}; -/** - * A block is a group of variables that must be moved together to improve - * the goal function without violating already active constraints. - * The variables in a block are spanned by a tree of active constraints. - */ class Block { typedef std::vector<Variable*> Variables; - typedef std::vector<Constraint*>::iterator Cit; - typedef std::vector<Variable*>::iterator Vit; + typedef std::vector<Constraint*> Constraints; + typedef Variables::iterator Vit; + typedef Constraints::iterator Cit; + typedef Constraints::const_iterator Cit_const; friend std::ostream& operator <<(std::ostream &os,const Block &b); public: Variables *vars; double posn; - double weight; - double wposn; - Block(Variable* const v=NULL); - virtual ~Block(void); - - /** - * finds the constraint with the minimum lagrange multiplier, that is, the constraint - * that most wants to split - */ - Constraint* findMinLM(); - + //double weight; + //double wposn; + PositionStats ps; + Block(Blocks *blocks, Variable* const v=NULL); + ~Block(void); + Constraint* findMinLM(); Constraint* findMinLMBetween(Variable* const lv, Variable* const rv); Constraint* findMinInConstraint(); Constraint* findMinOutConstraint(); void deleteMinInConstraint(); void deleteMinOutConstraint(); - double desiredWeightedPosition(); - - /** - * Merges b into this block across c. Can be either a - * right merge or a left merge - * @param b block to merge into this - * @param c constraint being merged - * @param distance separation required to satisfy c - */ - void merge(Block *b, Constraint *c, double dist); - - void merge(Block *b, Constraint *c); + void updateWeightedPosition(); + void merge(Block *b, Constraint *c, double dist); + Block* merge(Block *b, Constraint *c); void mergeIn(Block *b); void mergeOut(Block *b); - - /** - * Creates two new blocks, l and r, and splits this block across constraint c, - * placing the left subtree of constraints (and associated variables) into l - * and the right into r. - */ - void split(Block *&l, Block *&r, Constraint *c); - - /** - * Block needs to be split because of a violated constraint between vl and vr. - * We need to search the active constraint tree between l and r and find the constraint - * with min lagrangrian multiplier and split at that point. - * Returns the split constraint - */ - Constraint* splitBetween(Variable* vl, Variable* vr, Block* &lb, Block* &rb); - + void split(Block *&l, Block *&r, Constraint *c); + Constraint* splitBetween(Variable* vl, Variable* vr, Block* &lb, Block* &rb); void setUpInConstraints(); void setUpOutConstraints(); - - /** - * Computes the cost (squared euclidean distance from desired positions) of the - * current positions for variables in this block - */ - double cost(); - + double cost(); bool deleted; long timeStamp; - PairingHeap<Constraint*> *in; - PairingHeap<Constraint*> *out; - bool isActiveDirectedPathBetween(Variable* u, Variable *v); + PairingHeap<Constraint*,CompareConstraints> *in; + PairingHeap<Constraint*,CompareConstraints> *out; + bool getActivePathBetween(Constraints& path, Variable const* u, + Variable const* v, Variable const *w) const; + bool isActiveDirectedPathBetween( + Variable const* u, Variable const* v) const; + bool getActiveDirectedPathBetween(Constraints& path, Variable const * u, Variable const * v) const; private: typedef enum {NONE, LEFT, RIGHT} Direction; typedef std::pair<double, Constraint*> Pair; void reset_active_lm(Variable* const v, Variable* const u); - double compute_dfdv(Variable* const v, Variable* const u, - Constraint *&min_lm); - Pair compute_dfdv_between( - Variable*, Variable* const, Variable* const, - const Direction, bool); - bool canFollowLeft(Constraint *c, const Variable* const last); - bool canFollowRight(Constraint *c, const Variable* const last); - void populateSplitBlock(Block *b, Variable* const v, Variable* const u); - void addVariable(Variable* const v); - void setUpConstraintHeap(PairingHeap<Constraint*>* &h,bool in); -}; + void list_active(Variable* const v, Variable* const u); + double compute_dfdv(Variable* const v, Variable* const u); + double compute_dfdv(Variable* const v, Variable* const u, Constraint *&min_lm); + bool split_path(Variable*, Variable* const, Variable* const, + Constraint* &min_lm, bool desperation); + bool canFollowLeft(Constraint const* c, Variable const* last) const; + bool canFollowRight(Constraint const* c, Variable const* last) const; + void populateSplitBlock(Block *b, Variable* v, Variable const* u); + void addVariable(Variable* v); + void setUpConstraintHeap(PairingHeap<Constraint*,CompareConstraints>* &h,bool in); + // Parent container, that holds the blockTimeCtr. + Blocks *blocks; +}; } -#endif // SEEN_REMOVEOVERLAP_BLOCK_H -/* - Local Variables: - mode:c++ - c-file-style:"stroustrup" - c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) - indent-tabs-mode:nil - fill-column:99 - End: -*/ -// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 : + +#endif // VPSC_BLOCK_H diff --git a/src/libvpsc/blocks.cpp b/src/libvpsc/blocks.cpp index 7eff1e6c4..52e940ce7 100644 --- a/src/libvpsc/blocks.cpp +++ b/src/libvpsc/blocks.cpp @@ -1,180 +1,249 @@ /* - * A block structure defined over the variables. + * vim: ts=4 sw=4 et tw=0 wm=0 * - * Authors: - * Tim Dwyer <tgdwyer@gmail.com> + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. * - * Copyright (C) 2005 Authors + * Copyright (C) 2005-2012 Monash University * - * Released under GNU LGPL. Read the file 'COPYING' for more information. + * 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 +*/ + +/* + * @brief A block structure defined over the variables + * + * A block structure defined over the variables such that each block contains + * 1 or more variables, with the invariant that all constraints inside a block + * are satisfied by keeping the variables fixed relative to one another */ -#include "blocks.h" -#include "block.h" -#include "constraint.h" -#ifdef RECTANGLE_OVERLAP_LOGGING +#include "libvpsc/blocks.h" +#include "libvpsc/block.h" +#include "libvpsc/constraint.h" +#include "libvpsc/variable.h" +#include "libvpsc/assertions.h" + +#ifdef LIBVPSC_LOGGING #include <fstream> using std::ios; using std::ofstream; using std::endl; #endif -using std::set; using std::vector; using std::iterator; using std::list; using std::copy; +#define __NOTNAN(p) (p)==(p) namespace vpsc { -long blockTimeCtr; -Blocks::Blocks(const int n, Variable* const vs[]) : vs(vs),nvs(n) { - blockTimeCtr=0; - for(int i=0;i<nvs;i++) { - insert(new Block(vs[i])); - } +Blocks::Blocks(vector<Variable*> const &vs) : vs(vs),nvs(vs.size()) { + blockTimeCtr=0; + m_blocks.resize(nvs); + for(size_t i=0;i<nvs;i++) { + m_blocks[i] = new Block(this, vs[i]); + } } Blocks::~Blocks(void) { - blockTimeCtr=0; - for(set<Block*>::iterator i=begin();i!=end();++i) { - delete *i; - } - clear(); + blockTimeCtr=0; + size_t length = m_blocks.size(); + for (size_t i = 0; i < length; ++i) + { + delete m_blocks[i]; + } + m_blocks.clear(); } +/* + * returns a list of variables with total ordering determined by the constraint + * DAG + */ list<Variable*> *Blocks::totalOrder() { - list<Variable*> *order = new list<Variable*>; - for(int i=0;i<nvs;i++) { - vs[i]->visited=false; - } - for(int i=0;i<nvs;i++) { - if(vs[i]->in.size()==0) { - dfsVisit(vs[i],order); - } - } - return order; + list<Variable*> *order = new list<Variable*>; + for(size_t i=0;i<nvs;i++) { + vs[i]->visited=false; + } + for(size_t i=0;i<nvs;i++) { + if(vs[i]->in.size()==0) { + dfsVisit(vs[i],order); + } + } + return order; } // Recursive depth first search giving total order by pushing nodes in the DAG // onto the front of the list when we finish searching them void Blocks::dfsVisit(Variable *v, list<Variable*> *order) { - v->visited=true; - vector<Constraint*>::iterator it=v->out.begin(); - for(;it!=v->out.end();++it) { - Constraint *c=*it; - if(!c->right->visited) { - dfsVisit(c->right, order); - } - } -#ifdef RECTANGLE_OVERLAP_LOGGING - ofstream f(LOGFILE,ios::app); - f<<" order="<<*v<<endl; + v->visited=true; + vector<Constraint*>::iterator it=v->out.begin(); + for(;it!=v->out.end();++it) { + Constraint *c=*it; + if(!c->right->visited) { + dfsVisit(c->right, order); + } + } +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<" order="<<*v<<endl; #endif - order->push_front(v); + order->push_front(v); } - -void Blocks::mergeLeft(Block *r) { -#ifdef RECTANGLE_OVERLAP_LOGGING - ofstream f(LOGFILE,ios::app); - f<<"mergeLeft called on "<<*r<<endl; +/* + * Processes incoming constraints, most violated to least, merging with the + * neighbouring (left) block until no more violated constraints are found + */ +void Blocks::mergeLeft(Block *r) { +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"mergeLeft called on "<<*r<<endl; #endif - r->timeStamp=++blockTimeCtr; - r->setUpInConstraints(); - Constraint *c=r->findMinInConstraint(); - while (c != NULL && c->slack()<0) { -#ifdef RECTANGLE_OVERLAP_LOGGING - f<<"mergeLeft on constraint: "<<*c<<endl; + r->timeStamp=++blockTimeCtr; + r->setUpInConstraints(); + Constraint *c=r->findMinInConstraint(); + while (c != NULL && c->slack()<0) { +#ifdef LIBVPSC_LOGGING + f<<"mergeLeft on constraint: "<<*c<<endl; #endif - r->deleteMinInConstraint(); - Block *l = c->left->block; - if (l->in==NULL) l->setUpInConstraints(); - double dist = c->right->offset - c->left->offset - c->gap; - if (r->vars->size() < l->vars->size()) { - dist=-dist; - std::swap(l, r); - } - blockTimeCtr++; - r->merge(l, c, dist); - r->mergeIn(l); - r->timeStamp=blockTimeCtr; - removeBlock(l); - c=r->findMinInConstraint(); - } -#ifdef RECTANGLE_OVERLAP_LOGGING - f<<"merged "<<*r<<endl; + r->deleteMinInConstraint(); + Block *l = c->left->block; + if (l->in==NULL) l->setUpInConstraints(); + double dist = c->right->offset - c->left->offset - c->gap; + if (r->vars->size() < l->vars->size()) { + dist=-dist; + std::swap(l, r); + } + blockTimeCtr++; + r->merge(l, c, dist); + r->mergeIn(l); + r->timeStamp=blockTimeCtr; + removeBlock(l); + c=r->findMinInConstraint(); + } +#ifdef LIBVPSC_LOGGING + f<<"merged "<<*r<<endl; #endif -} - -void Blocks::mergeRight(Block *l) { -#ifdef RECTANGLE_OVERLAP_LOGGING - ofstream f(LOGFILE,ios::app); - f<<"mergeRight called on "<<*l<<endl; -#endif - l->setUpOutConstraints(); - Constraint *c = l->findMinOutConstraint(); - while (c != NULL && c->slack()<0) { -#ifdef RECTANGLE_OVERLAP_LOGGING - f<<"mergeRight on constraint: "<<*c<<endl; +} +/* + * Symmetrical to mergeLeft + */ +void Blocks::mergeRight(Block *l) { +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"mergeRight called on "<<*l<<endl; +#endif + l->setUpOutConstraints(); + Constraint *c = l->findMinOutConstraint(); + while (c != NULL && c->slack()<0) { +#ifdef LIBVPSC_LOGGING + f<<"mergeRight on constraint: "<<*c<<endl; #endif - l->deleteMinOutConstraint(); - Block *r = c->right->block; - r->setUpOutConstraints(); - double dist = c->left->offset + c->gap - c->right->offset; - if (l->vars->size() > r->vars->size()) { - dist=-dist; - std::swap(l, r); - } - l->merge(r, c, dist); - l->mergeOut(r); - removeBlock(r); - c=l->findMinOutConstraint(); - } -#ifdef RECTANGLE_OVERLAP_LOGGING - f<<"merged "<<*l<<endl; + l->deleteMinOutConstraint(); + Block *r = c->right->block; + r->setUpOutConstraints(); + double dist = c->left->offset + c->gap - c->right->offset; + if (l->vars->size() > r->vars->size()) { + dist=-dist; + std::swap(l, r); + } + l->merge(r, c, dist); + l->mergeOut(r); + removeBlock(r); + c=l->findMinOutConstraint(); + } +#ifdef LIBVPSC_LOGGING + f<<"merged "<<*l<<endl; #endif } void Blocks::removeBlock(Block *doomed) { - doomed->deleted=true; - //erase(doomed); -} -void Blocks::cleanup() { - vector<Block*> bcopy(begin(),end()); - for(vector<Block*>::iterator i=bcopy.begin();i!=bcopy.end();++i) { - Block *b=*i; - if(b->deleted) { - erase(b); - delete b; - } - } + doomed->deleted=true; + //erase(doomed); } +// Clears up deleted blocks from the blocks list. +void Blocks::cleanup(void) +{ + // We handle removal of items in-place by doing a single linear pass over + // the vector. We use two indexes, j to refer to elements we've checked + // from the original list and i to refer to the current position we are + // writing in the updated list. + size_t i = 0; + + // For all items in the current blocks list... + size_t length = m_blocks.size(); + for (size_t j = 0; j < length; ) + { + if (m_blocks[j]->deleted) + { + // The element is deleted, so free it and increment j. + delete m_blocks[j]; + ++j; + } + else + { + // The current element is still valid. + if (j > i) + { + // If we've not looking at same element, then copy from j to i. + m_blocks[i] = m_blocks[j]; + } + // Increment both indexes. + ++i; + ++j; + } + } + m_blocks.resize(i); +} +/* + * Splits block b across constraint c into two new blocks, l and r (c's left + * and right sides respectively) + */ void Blocks::split(Block *b, Block *&l, Block *&r, Constraint *c) { - b->split(l,r,c); -#ifdef RECTANGLE_OVERLAP_LOGGING - ofstream f(LOGFILE,ios::app); - f<<"Split left: "<<*l<<endl; - f<<"Split right: "<<*r<<endl; + b->split(l,r,c); + m_blocks.push_back(l); + m_blocks.push_back(r); +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"Split left: "<<*l<<endl; + f<<"Split right: "<<*r<<endl; #endif - r->posn = b->posn; - r->wposn = r->posn * r->weight; - mergeLeft(l); - // r may have been merged! - r = c->right->block; - r->wposn = r->desiredWeightedPosition(); - r->posn = r->wposn / r->weight; - mergeRight(r); - removeBlock(b); + r->posn = b->posn; + //COLA_ASSERT(r->weight!=0); + //r->wposn = r->posn * r->weight; + mergeLeft(l); + // r may have been merged! + r = c->right->block; + r->updateWeightedPosition(); + //r->posn = r->wposn / r->weight; + mergeRight(r); + removeBlock(b); - insert(l); - insert(r); + COLA_ASSERT(__NOTNAN(l->posn)); + COLA_ASSERT(__NOTNAN(r->posn)); } - +/* + * returns the cost total squared distance of variables from their desired + * positions + */ double Blocks::cost() { - double c = 0; - for(set<Block*>::iterator i=begin();i!=end();++i) { - c += (*i)->cost(); - } - return c; + double c = 0; + size_t length = m_blocks.size(); + for (size_t i = 0; i < length; ++i) + { + c += m_blocks[i]->cost(); + } + return c; } } diff --git a/src/libvpsc/blocks.h b/src/libvpsc/blocks.h index b711a529f..a3613db2f 100644 --- a/src/libvpsc/blocks.h +++ b/src/libvpsc/blocks.h @@ -1,94 +1,96 @@ /* - * Authors: - * Tim Dwyer <tgdwyer@gmail.com> + * vim: ts=4 sw=4 et tw=0 wm=0 * - * Copyright (C) 2005 Authors + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. + * + * Copyright (C) 2005-2012 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 +*/ + +/* + * @brief A block structure defined over the variables + * + * A block structure defined over the variables such that each block contains + * 1 or more variables, with the invariant that all constraints inside a block + * are satisfied by keeping the variables fixed relative to one another * - * Released under GNU LGPL. Read the file 'COPYING' for more information. */ -#ifndef SEEN_REMOVEOVERLAP_BLOCKS_H -#define SEEN_REMOVEOVERLAP_BLOCKS_H +#ifndef VPSC_BLOCKS_H +#define VPSC_BLOCKS_H -#ifdef RECTANGLE_OVERLAP_LOGGING -#define LOGFILE "cRectangleOverlap.log" +#ifdef LIBVPSC_LOGGING +#define LOGFILE "libvpsc.log" #endif -#include <set> #include <list> +#include <vector> -namespace vpsc { +// size_t is strangely not defined on some older MinGW GCC versions. +#include <cstddef> +namespace vpsc { class Block; class Variable; class Constraint; - -/** +/* * A block structure defined over the variables such that each block contains * 1 or more variables, with the invariant that all constraints inside a block - * are satisfied by keeping the variables fixed relative to one another. - * - * @todo check on this class being copy-n-paste duplicated. + * are satisfied by keeping the variables fixed relative to one another */ -class Blocks : public std::set<Block*> +class Blocks { public: - Blocks(const int n, Variable* const vs[]); - - virtual ~Blocks(void); - - /** - * Processes incoming constraints, most violated to least, merging with the - * neighbouring (left) block until no more violated constraints are found. - */ - void mergeLeft(Block *r); - - /** - * Symmetrical to mergeLeft. - * @see mergeLeft - */ - void mergeRight(Block *l); - - /** - * Splits block b across constraint c into two new blocks, l and r (c's left - * and right sides respectively). - */ - void split(Block *b, Block *&l, Block *&r, Constraint *c); - - /** - * Returns a list of variables with total ordering determined by the constraint - * DAG. - */ - std::list<Variable*> *totalOrder(); - - void cleanup(); - - /** - * Returns the cost total squared distance of variables from their desired - * positions. - */ - double cost(); - + Blocks(std::vector<Variable*> const &vs); + ~Blocks(void); + void mergeLeft(Block *r); + void mergeRight(Block *l); + void split(Block *b, Block *&l, Block *&r, Constraint *c); + std::list<Variable*> *totalOrder(); + void cleanup(); + double cost(); + + size_t size() const; + Block *at(size_t index) const; + void insert(Block *block); + + long blockTimeCtr; private: - void dfsVisit(Variable *v, std::list<Variable*> *order); + void dfsVisit(Variable *v, std::list<Variable*> *order); + void removeBlock(Block *doomed); + + std::vector<Block*> m_blocks; + std::vector<Variable*> const &vs; + size_t nvs; +}; - void removeBlock(Block *doomed); +inline size_t Blocks::size() const +{ + return m_blocks.size(); +} - Variable* const *vs; +inline Block *Blocks::at(size_t index) const +{ + return m_blocks[index]; +} - int nvs; -}; +inline void Blocks::insert(Block *block) +{ + m_blocks.push_back(block); +} -extern long blockTimeCtr; } -#endif // SEEN_REMOVEOVERLAP_BLOCKS_H -/* - Local Variables: - mode:c++ - c-file-style:"stroustrup" - c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) - indent-tabs-mode:nil - fill-column:99 - End: -*/ -// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 : +#endif // VPSC_BLOCKS_H diff --git a/src/libvpsc/cbuffer.cpp b/src/libvpsc/cbuffer.cpp new file mode 100644 index 000000000..676bad304 --- /dev/null +++ b/src/libvpsc/cbuffer.cpp @@ -0,0 +1,95 @@ +/* + * 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 <cfloat> + +#include "libvpsc/cbuffer.h" +#include "libvpsc/constraint.h" +#include "libvpsc/assertions.h" + +namespace vpsc { + static const double ZERO_UPPERBOUND=-0.0000001; + void CBuffer::load() { + size=0; + double buffMaxSlack=-DBL_MAX; + unsigned buffMaxSlackPos=0; + for(Constraints::iterator i=master_list.begin(); + i!=master_list.end();++i) { + Constraint *c=*i; + double slack = c->slack(); + if(c->equality||slack<ZERO_UPPERBOUND) { + if(size<maxsize) { + // make sure buffer is full + buffer[size]=c; + if(slack>buffMaxSlack) { + buffMaxSlack=slack; + buffMaxSlackPos=size; + } + size++; + } else { + // if c is more violated than the least violated + // constraint in the buffer then replace it + buffer[buffMaxSlackPos]=c; + // need to search the buffer for the new least + // violated constraint + buffMaxSlack=-DBL_MAX; + for(unsigned i=0;i<size;i++) { + c=buffer[i]; + if(!c->equality&&buffMaxSlack < c->slack()) { + buffMaxSlack = slack; + buffMaxSlackPos = i; + } + } + } + } + } + } + Constraint* CBuffer::mostViolated() { + Constraint* v=NULL; + while(true) { + if(size==0) { + load(); + if(size==0) break; + } + double minSlack=DBL_MAX; + int i,deletePos=-1; + for(i=0;i<(int)size;i++) { + Constraint *c=buffer[i]; + double slack = c->slack(); + if(!(c->equality||slack < ZERO_UPPERBOUND)) { + COLA_ASSERT(size>0); + buffer[i--]=buffer[--size]; + } else if(c->equality||slack < minSlack) { + v=c; + deletePos=i; + minSlack=slack; + } + } + if(deletePos>=0) { + COLA_ASSERT(size>0); + buffer[deletePos]=buffer[--size]; + break; + } + } + return v; + } +} diff --git a/src/libvpsc/cbuffer.h b/src/libvpsc/cbuffer.h new file mode 100644 index 000000000..9cf302cbf --- /dev/null +++ b/src/libvpsc/cbuffer.h @@ -0,0 +1,49 @@ +/* + * 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 + * + */ +#ifndef VPSC_CBUFFER_H +#define VPSC_CBUFFER_H + +#include <vector> + +namespace vpsc { + class Constraint; + class CBuffer { + public: + CBuffer(std::vector<Constraint*>& l, + const unsigned maxsize=5) + : master_list(l), maxsize(maxsize), size(0) { + buffer.resize(maxsize); + load(); + } + void reset() { size=0; } + void load(); + Constraint* mostViolated(); + private: + std::vector<Constraint*>& master_list; + std::vector<Constraint*> buffer; + const unsigned maxsize; + unsigned size; + }; +} + +#endif // VPSC_CBUFFER_H + diff --git a/src/libvpsc/constraint.cpp b/src/libvpsc/constraint.cpp index 0ec06dfac..f1b7f0571 100644 --- a/src/libvpsc/constraint.cpp +++ b/src/libvpsc/constraint.cpp @@ -1,14 +1,36 @@ /* - * Authors: - * Tim Dwyer <tgdwyer@gmail.com> + * vim: ts=4 sw=4 et tw=0 wm=0 * - * Copyright (C) 2005 Authors + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. * - * Released under GNU LGPL. Read the file 'COPYING' for more information. - */ + * 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 "constraint.h" + +#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), @@ -16,31 +38,181 @@ Constraint::Constraint(Variable *left, Variable *right, double gap, bool equalit gap(gap), timeStamp(0), active(false), - visited(false), - equality(equality) + equality(equality), + unsatisfiable(false), + needsScaling(true), + creator(NULL) { - left->out.push_back(this); - right->in.push_back(this); + // 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() { - 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); + // 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) { - if(&c==NULL) { - os<<"NULL"; - } else { - const char *type=c.equality?"=":"<="; - os<<*c.left<<"+"<<c.gap<<type<<*c.right<<"("<<c.slack()<<")"<<(c.active?"-active":""); - } - return os; + 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; } + + } diff --git a/src/libvpsc/constraint.h b/src/libvpsc/constraint.h index a3173359c..271a2cfce 100644 --- a/src/libvpsc/constraint.h +++ b/src/libvpsc/constraint.h @@ -1,62 +1,139 @@ /* - * Authors: - * Tim Dwyer <tgdwyer@gmail.com> + * vim: ts=4 sw=4 et tw=0 wm=0 * - * Copyright (C) 2005 Authors + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. * - * Released under GNU LGPL. Read the file 'COPYING' for more information. - */ + * 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 +*/ + + +#ifndef VPSC_CONSTRAINT_H +#define VPSC_CONSTRAINT_H -#ifndef SEEN_REMOVEOVERLAP_CONSTRAINT_H -#define SEEN_REMOVEOVERLAP_CONSTRAINT_H +// cmath needs ::strcpy_s under MinGW so include cstring. +#include <cstring> +#include <cfloat> #include <iostream> -#include "variable.h" +#include <vector> +#include <sstream> + +#include "libvpsc/variable.h" + namespace vpsc { -/** - * A constraint determines a minimum or exact spacing required between - * two variables. - * - */ +class Variable; +typedef std::vector<Variable *> Variables; + +//! @brief A constraint determines a minimum or exact spacing required between +//! two Variable objects. +//! class Constraint { friend std::ostream& operator <<(std::ostream &os,const Constraint &c); public: - Variable *left; + //! @brief Constructs a minimum or exact spacing constraint between two + //! Variable objects. + //! + //! (left + gap < right) or (left + gap == right) + //! + //! @param[in] left The left Variable. + //! @param[in] right The right Variable. + //! @param[in] gap The minimum or exact distance to separate the + //! variables by. + //! @param[in] equality Whether the separation is an exact distance or + //! not. The default is false. + Constraint(Variable *left, Variable *right, double gap, + bool equality = false); + ~Constraint(); + + /** + * @brief Returns a textual description of the constraint. + * + * @return A string describing the constraint. + */ + std::string toString(void) const + { + std::stringstream stream; + stream << "Constraint: var(" << left->id << ") "; + if (gap < 0) + { + stream << "- " << -gap << " "; + } + else + { + stream << "+ " << gap << " "; + } + stream << ((equality) ? "==" : "<="); + stream << " var(" << right->id << ") "; + return stream.str(); + } + + inline double slack(void) const + { + if (unsatisfiable) + { + return DBL_MAX; + } + if (needsScaling) + { + return right->scale * right->position() - gap - + left->scale * left->position(); + } + COLA_ASSERT(left->scale == 1); + COLA_ASSERT(right->scale == 1); + return right->unscaledPosition() - gap - left->unscaledPosition(); + } + + //! @brief The left Variable. + Variable *left; + //! @brief The right Variable. Variable *right; + //! @brief The minimum or exact distance to separate the variables by. double gap; double lm; - Constraint(Variable *left, Variable *right, double gap, bool equality=false); - virtual ~Constraint(); - inline double slack() const { return right->position() - gap - left->position(); } long timeStamp; bool active; - bool visited; - bool equality; + //! @brief Whether the separation is an exact distance or not. + const bool equality; + //! @brief Denote whether this constraint was unsatisifable (once the VPSC + //! instance has been solved or satisfied). + bool unsatisfiable; + bool needsScaling; + void *creator; }; -#include <float.h> -#include "block.h" -static inline bool compareConstraints(Constraint *const &l, Constraint *const &r) { - 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; -} + +class CompareConstraints { +public: + bool operator() (Constraint *const &l, Constraint *const &r) const; +}; + +//! @brief A vector of pointers to Constraint objects. +typedef std::vector<Constraint*> Constraints; + +/** @brief Given a set of variables and constraints, returns a modified set + * of constraints with all redundant equality constraints removed. + * + * VPSC doesn't work well with redundant equality constraints, usually showing + * them as unsatisfiable. This function looks for cycles of equality + * constraints and removes the redundant ones. + */ +extern Constraints constraintsRemovingRedundantEqualities( + const Variables& vars, const Constraints& constraints); + } -#endif // SEEN_REMOVEOVERLAP_CONSTRAINT_H +#endif // VPSC_CONSTRAINT_H diff --git a/src/libvpsc/doc/description.doc b/src/libvpsc/doc/description.doc new file mode 100644 index 000000000..46a21b093 --- /dev/null +++ b/src/libvpsc/doc/description.doc @@ -0,0 +1,36 @@ +/*! + +\if LIBVPSC_DOC +@mainpage libvpsc: Variable Placement with Separation Constraints solver +\endif +\if ADAPTAGRAMS_DOC +@page libvpsc libvpsc — Overview +\endif + + +libvpsc is a cross-platform C++ library for solving for the Variable Placement with Separation Constraints problem. This is a quadratic programming problem in which the squared differences between a placement vector and some ideal placement are minimised subject to a set of separation constraints. This is very useful in a number of layout problems. + +libvpsc is part of the +<a href="http://www.adaptagrams.org/">Adaptagrams project</a>. +There are no official releases yet, though the code is stable and +available from the Adaptagrams +<a href="https://github.com/mjwybrow/adaptagrams">github +repository</a>. + +The API is documented using Doxygen. The documentation you are currently +reading can be obtained by running doxygen in the cola directory. + +libcola is written and maintained by +<a href="http://marvl.infotech.monash.edu/~mwybrow/">Michael Wybrow</a> and +<a href="http://marvl.infotech.monash.edu/~dwyer/">Tim Dwyer</a>, +members of <a href="http://marvl.infotech.monash.edu/">MArVL: the Monash Adaptive Visualisation Lab</a> at Monash University, Australia. + +The algorithms used for VPSC are described in the following papers. If you use libcola, please cite the relevant paper. +- Tim Dwyer, Kim Marriott, and Peter J. Stuckey. Fast node overlap removal.\n + In Proceedings 13th International Symposium on Graph Drawing (GD '05),\n + volume 3843 of LNCS, pages 153-164. Springer, 2006. + + +*/ + + diff --git a/src/libvpsc/exceptions.h b/src/libvpsc/exceptions.h new file mode 100644 index 000000000..5f66afe26 --- /dev/null +++ b/src/libvpsc/exceptions.h @@ -0,0 +1,36 @@ +/* + * 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. + * +*/ + +#ifndef VPSC_EXCEPTIONS_H +#define VPSC_EXCEPTIONS_H + +#include <vector> +namespace vpsc { +class Constraint; +struct UnsatisfiableException { + std::vector<Constraint*> path; +}; +struct UnsatisfiedConstraint { + UnsatisfiedConstraint(Constraint& c):c(c) {} + Constraint& c; +}; +} // namespace vpsc + +#endif // VPSC_EXCEPTIONS_H diff --git a/src/libvpsc/generate-constraints.cpp b/src/libvpsc/generate-constraints.cpp deleted file mode 100644 index 288e7ed53..000000000 --- a/src/libvpsc/generate-constraints.cpp +++ /dev/null @@ -1,309 +0,0 @@ -/** - * @file - * Functions to automatically generate constraints for the - * rectangular node overlap removal problem. - */ -/* - * - * Authors: - * Tim Dwyer <tgdwyer@gmail.com> - * - * Copyright (C) 2005 Authors - * - * Released under GNU LGPL. Read the file 'COPYING' for more information. - */ - -#include <set> -#include <cassert> -#include <cstdlib> -#include "generate-constraints.h" -#include "constraint.h" - -#include <2geom/math-utils.h> - -using std::set; -using std::vector; - -namespace vpsc { -std::ostream& operator <<(std::ostream &os, const Rectangle &r) { - os << "{"<<r.minX<<","<<r.maxX<<","<<r.minY<<","<<r.maxY<<"},"; - return os; -} - -Rectangle::Rectangle(double x, double X, double y, double Y) -: minX(x),maxX(X),minY(y),maxY(Y) { - assert(x<=X); - assert(y<=Y); -} - -struct Node; -struct CmpNodePos { bool operator()(const Node* u, const Node* v) const; }; - -typedef set<Node*,CmpNodePos> NodeSet; - -struct Node { - Variable *v; - Rectangle *r; - double pos; - Node *firstAbove, *firstBelow; - NodeSet *leftNeighbours, *rightNeighbours; - Node(Variable *v, Rectangle *r, double p) : v(v),r(r),pos(p) { - firstAbove=firstBelow=NULL; - leftNeighbours=rightNeighbours=NULL; - assert(r->width()<1e40); - } - ~Node() { - delete leftNeighbours; - delete rightNeighbours; - } - void addLeftNeighbour(Node *u) { - leftNeighbours->insert(u); - } - void addRightNeighbour(Node *u) { - rightNeighbours->insert(u); - } - void setNeighbours(NodeSet *left, NodeSet *right) { - leftNeighbours=left; - rightNeighbours=right; - for(NodeSet::iterator i=left->begin();i!=left->end();++i) { - Node *v=*(i); - v->addRightNeighbour(this); - } - for(NodeSet::iterator i=right->begin();i!=right->end();++i) { - Node *v=*(i); - v->addLeftNeighbour(this); - } - } -}; -bool CmpNodePos::operator() (const Node* u, const Node* v) const { - if (u->pos < v->pos) { - return true; - } - if (v->pos < u->pos) { - return false; - } - if (IS_NAN(u->pos) != IS_NAN(v->pos)) { - return IS_NAN(u->pos); - } - return u < v; - - /* I don't know how important it is to handle NaN correctly - * (e.g. we probably handle it badly in other code anyway, and - * in any case the best we can hope for is to reduce the - * badness of other nodes). - * - * Nevertheless, we try to do the right thing here and in - * event comparison. The issue is that (on platforms with - * ieee floating point comparison) NaN compares neither less - * than nor greater than any other number, yet sort wants a - * well-defined ordering. In particular, we want to ensure - * transitivity of equivalence, which normally wouldn't be - * guaranteed if the "middle" item in the transitivity - * involves a NaN. (NaN is neither less than nor greater than - * other numbers, so tends to be considered as equal to all - * other numbers: even unequal numbers.) - */ -} - -static NodeSet* getLeftNeighbours(NodeSet &scanline,Node *v) { - NodeSet *leftv = new NodeSet; - NodeSet::iterator i=scanline.find(v); - while(i--!=scanline.begin()) { - Node *u=*(i); - if(u->r->overlapX(v->r)<=0) { - leftv->insert(u); - return leftv; - } - if(u->r->overlapX(v->r)<=u->r->overlapY(v->r)) { - leftv->insert(u); - } - } - return leftv; -} -static NodeSet* getRightNeighbours(NodeSet &scanline,Node *v) { - NodeSet *rightv = new NodeSet; - NodeSet::iterator i=scanline.find(v); - for(++i;i!=scanline.end(); ++i) { - Node *u=*(i); - if(u->r->overlapX(v->r)<=0) { - rightv->insert(u); - return rightv; - } - if(u->r->overlapX(v->r)<=u->r->overlapY(v->r)) { - rightv->insert(u); - } - } - return rightv; -} - -typedef enum {Open, Close} EventType; -struct Event { - EventType type; - Node *v; - double pos; - Event(EventType t, Node *v, double p) : type(t),v(v),pos(p) {}; -}; -Event **events; -static int compare_events(const void *a, const void *b) { - Event *ea=*(Event**)a; - Event *eb=*(Event**)b; - if(ea->v->r==eb->v->r) { - // when comparing opening and closing from the same rect - // open must come first - if(ea->type==Open) return -1; - return 1; - } else if(ea->pos > eb->pos) { - return 1; - } else if(ea->pos < eb->pos) { - return -1; - } else if(IS_NAN(ea->pos) != IS_NAN(ea->pos)) { - /* See comment in CmpNodePos. */ - return ( IS_NAN(ea->pos) - ? -1 - : 1 ); - } - return 0; -} - -/** - * Prepares constraints in order to apply VPSC horizontally. Assumes variables have already been created. - * useNeighbourLists determines whether or not a heuristic is used to deciding whether to resolve - * all overlap in the x pass, or leave some overlaps for the y pass. - */ -int generateXConstraints(const int n, Rectangle** rs, Variable** vars, Constraint** &cs, const bool useNeighbourLists) { - events=new Event*[2*n]; - int i,m,ctr=0; - for(i=0;i<n;i++) { - vars[i]->desiredPosition=rs[i]->getCentreX(); - Node *v = new Node(vars[i],rs[i],rs[i]->getCentreX()); - events[ctr++]=new Event(Open,v,rs[i]->getMinY()); - events[ctr++]=new Event(Close,v,rs[i]->getMaxY()); - } - qsort((Event*)events, (size_t)2*n, sizeof(Event*), compare_events ); - - NodeSet scanline; - vector<Constraint*> constraints; - for(i=0;i<2*n;i++) { - Event *e=events[i]; - Node *v=e->v; - if(e->type==Open) { - scanline.insert(v); - if(useNeighbourLists) { - v->setNeighbours( - getLeftNeighbours(scanline,v), - getRightNeighbours(scanline,v) - ); - } else { - NodeSet::iterator it=scanline.find(v); - if(it--!=scanline.begin()) { - Node *u=*it; - v->firstAbove=u; - u->firstBelow=v; - } - it=scanline.find(v); - if(++it!=scanline.end()) { - Node *u=*it; - v->firstBelow=u; - u->firstAbove=v; - } - } - } else { - // Close event - if(useNeighbourLists) { - for(NodeSet::iterator i=v->leftNeighbours->begin(); - i!=v->leftNeighbours->end();i++ - ) { - Node *u=*i; - double sep = (v->r->width()+u->r->width())/2.0; - constraints.push_back(new Constraint(u->v,v->v,sep)); - u->rightNeighbours->erase(v); - } - - for(NodeSet::iterator i=v->rightNeighbours->begin(); - i!=v->rightNeighbours->end();i++ - ) { - Node *u=*i; - double sep = (v->r->width()+u->r->width())/2.0; - constraints.push_back(new Constraint(v->v,u->v,sep)); - u->leftNeighbours->erase(v); - } - } else { - Node *l=v->firstAbove, *r=v->firstBelow; - if(l!=NULL) { - double sep = (v->r->width()+l->r->width())/2.0; - constraints.push_back(new Constraint(l->v,v->v,sep)); - l->firstBelow = v->firstBelow; - } - if(r!=NULL) { - double sep = (v->r->width()+r->r->width())/2.0; - constraints.push_back(new Constraint(v->v,r->v,sep)); - r->firstAbove = v->firstAbove; - } - } - scanline.erase(v); - delete v; - } - delete e; - } - delete [] events; - cs=new Constraint*[m=constraints.size()]; - for(i=0;i<m;i++) cs[i]=constraints[i]; - return m; -} - -/** - * Prepares constraints in order to apply VPSC vertically to remove ALL overlap. - */ -int generateYConstraints(const int n, Rectangle** rs, Variable** vars, Constraint** &cs) { - events=new Event*[2*n]; - int ctr=0,i,m; - for(i=0;i<n;i++) { - vars[i]->desiredPosition=rs[i]->getCentreY(); - Node *v = new Node(vars[i],rs[i],rs[i]->getCentreY()); - events[ctr++]=new Event(Open,v,rs[i]->getMinX()); - events[ctr++]=new Event(Close,v,rs[i]->getMaxX()); - } - qsort((Event*)events, (size_t)2*n, sizeof(Event*), compare_events ); - NodeSet scanline; - vector<Constraint*> constraints; - for(i=0;i<2*n;i++) { - Event *e=events[i]; - Node *v=e->v; - if(e->type==Open) { - scanline.insert(v); - NodeSet::iterator i=scanline.find(v); - if(i--!=scanline.begin()) { - Node *u=*i; - v->firstAbove=u; - u->firstBelow=v; - } - i=scanline.find(v); - if(++i!=scanline.end()) { - Node *u=*i; - v->firstBelow=u; - u->firstAbove=v; - } - } else { - // Close event - Node *l=v->firstAbove, *r=v->firstBelow; - if(l!=NULL) { - double sep = (v->r->height()+l->r->height())/2.0; - constraints.push_back(new Constraint(l->v,v->v,sep)); - l->firstBelow=v->firstBelow; - } - if(r!=NULL) { - double sep = (v->r->height()+r->r->height())/2.0; - constraints.push_back(new Constraint(v->v,r->v,sep)); - r->firstAbove=v->firstAbove; - } - scanline.erase(v); - delete v; - } - delete e; - } - delete [] events; - cs=new Constraint*[m=constraints.size()]; - for(i=0;i<m;i++) cs[i]=constraints[i]; - return m; -} -} diff --git a/src/libvpsc/generate-constraints.h b/src/libvpsc/generate-constraints.h deleted file mode 100644 index b8d7cdcd9..000000000 --- a/src/libvpsc/generate-constraints.h +++ /dev/null @@ -1,84 +0,0 @@ -/** - * @file - * Functions to automatically generate constraints for the - * rectangular node overlap removal problem. - */ -/* TODO replace file comment with appropriate doc comment on vpsc::Rectangle */ -/* - * - * Authors: - * Tim Dwyer <tgdwyer@gmail.com> - * - * Copyright (C) 2005 Authors - * - * Released under GNU LGPL. Read the file 'COPYING' for more information. - */ -#ifndef SEEN_REMOVEOVERLAP_GENERATE_CONSTRAINTS_H -#define SEEN_REMOVEOVERLAP_GENERATE_CONSTRAINTS_H -#include <iostream> - -namespace vpsc { -class Rectangle { - friend std::ostream& operator <<(std::ostream &os, const Rectangle &r); -public: - static double xBorder,yBorder; - Rectangle(double x, double X, double y, double Y); - double getMaxX() const { return maxX+xBorder; } - double getMaxY() const { return maxY+yBorder; } - double getMinX() const { return minX; } - double getMinY() const { return minY; } - double getMinD(unsigned const d) const { - return ( d == 0 ? getMinX() : getMinY() ); - } - double getMaxD(unsigned const d) const { - return ( d == 0 ? getMaxX() : getMaxY() ); - } - double getCentreX() const { return minX+width()/2.0; } - double getCentreY() const { return minY+height()/2.0; } - double width() const { return getMaxX()-minX; } - double height() const { return getMaxY()-minY; } - static void setXBorder(double x) {xBorder=x;} - static void setYBorder(double y) {yBorder=y;} - void moveCentreX(double x) { - moveMinX(x-width()/2.0); - } - void moveCentreY(double y) { - moveMinY(y-height()/2.0); - } - void moveMinX(double x) { - maxX=x+width()-xBorder; - minX=x; - } - void moveMinY(double y) { - maxY=y+height()-yBorder; - minY=y; - } - inline double overlapX(Rectangle *r) const { - if (getCentreX() <= r->getCentreX() && r->minX < getMaxX()) - return getMaxX() - r->minX; - if (r->getCentreX() <= getCentreX() && minX < r->getMaxX()) - return r->getMaxX() - minX; - return 0; - } - inline double overlapY(Rectangle *r) const { - if (getCentreY() <= r->getCentreY() && r->minY < getMaxY()) - return getMaxY() - r->minY; - if (r->getCentreY() <= getCentreY() && minY < r->getMaxY()) - return r->getMaxY() - minY; - return 0; - } -private: - double minX,maxX,minY,maxY; -}; - - -class Variable; -class Constraint; - -// returns number of constraints generated -int generateXConstraints(const int n, Rectangle** rs, Variable** vars, Constraint** &cs, const bool useNeighbourLists); -int generateYConstraints(const int n, Rectangle** rs, Variable** vars, Constraint** &cs); - -} - -#endif // SEEN_REMOVEOVERLAP_GENERATE_CONSTRAINTS_H diff --git a/src/libvpsc/isnan.h b/src/libvpsc/isnan.h new file mode 100644 index 000000000..1e32b8a7a --- /dev/null +++ b/src/libvpsc/isnan.h @@ -0,0 +1,74 @@ +/* + * 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. + * +*/ + +#ifndef VPSC_ISNAN_H +#define VPSC_ISNAN_H + +/* + * Temporary fix for various misdefinitions of isnan(). + * isnan() is becoming undef'd in some .h files. + * #include this last in your .cpp file to get it right. + * + * The problem is that isnan and isfinite are part of C99 but aren't part of + * the C++ standard (which predates C99). + * + * Authors: + * Inkscape groupies and obsessive-compulsives + * + * Copyright (C) 2004 authors + * + * Released under GNU LGPL, read the file 'LICENSE' for more information + * + * 2005 modification hereby placed in public domain. Probably supercedes + * the 2004 copyright for the code itself. + */ + +#include <cmath> +#include <cfloat> + +#if defined(__isnan) +# define isNaN(_a) (__isnan(_a)) /* MacOSX/Darwin definition < 10.4 */ +#elif defined(WIN32) || defined(_isnan) +# define isNaN(_a) (_isnan(_a)) /* Win32 definition */ +#elif defined(isnan) || defined(__FreeBSD__) +# define isNaN(_a) (isnan(_a)) /* GNU definition */ +#else +# define isNaN(_a) (std::isnan(_a)) +#endif +/* If the above doesn't work, then try (a != a). + * Also, please report a bug as per http://www.inkscape.org/report_bugs.php, + * giving information about what platform and compiler version you're using. + */ + + +#if defined(__isfinite) +# define isFinite(_a) (__isfinite(_a)) /* MacOSX/Darwin definition < 10.4 */ +#elif defined(isfinite) +# define isFinite(_a) (isfinite(_a)) +#else +# define isFinite(_a) (std::isfinite(_a)) +#endif +/* If the above doesn't work, then try (finite(_a) && !isNaN(_a)) or (!isNaN((_a) - (_a))). + * Also, please report a bug as per http://www.inkscape.org/report_bugs.php, + * giving information about what platform and compiler version you're using. + */ + + +#endif /* VPSC_ISNAN_H */ diff --git a/src/libvpsc/libvpsc.pc.in b/src/libvpsc/libvpsc.pc.in new file mode 100644 index 000000000..9b6ff52ba --- /dev/null +++ b/src/libvpsc/libvpsc.pc.in @@ -0,0 +1,12 @@ +prefix=@prefix@ +exec_prefix=@exec_prefix@ +libdir=@libdir@ +includedir=@includedir@ + +Name: libvpsc +Description: A solver for the Variable Placement with Separation Constraints problem. +URL: http://www.adaptagrams.org/ +Version: @VERSION@ +Requires: +Libs: -L${libdir} -lvpsc +Cflags: -I${includedir}/libvpsc
\ No newline at end of file diff --git a/src/libvpsc/linesegment.h b/src/libvpsc/linesegment.h new file mode 100644 index 000000000..caca3a2bb --- /dev/null +++ b/src/libvpsc/linesegment.h @@ -0,0 +1,138 @@ +/* + * 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. + * +*/ + +//////////////////////////////////////////////////////////////////////////////// +// +// 2D Line Segment Intersection example +// Implementation of the theory provided by Paul Bourke +// +// Written by Damian Coventry +// Tuesday, 9 January 2007 +// +//////////////////////////////////////////////////////////////////////////////// + +#ifndef VPSC_LINESEGMENT_H +#define VPSC_LINESEGMENT_H + +namespace linesegment { +class Vector +{ +public: + double x_, y_; + + Vector(double f = 0.0f) + : x_(f), y_(f) {} + + Vector(double x, double y) + : x_(x), y_(y) {} +}; + +class LineSegment +{ +public: + Vector begin_; + Vector end_; + + LineSegment(const Vector& begin, const Vector& end) + : begin_(begin), end_(end) {} + + enum IntersectResult { PARALLEL, COINCIDENT, NOT_INTERSECTING, INTERSECTING }; + + IntersectResult Intersect(const LineSegment& other_line, Vector& intersection) + { + double dx1=end_.x_ - begin_.x_; + double dy1=end_.y_ - begin_.y_; + double dx2=other_line.end_.x_ - other_line.begin_.x_; + double dy2=other_line.end_.y_ - other_line.begin_.y_; + + double denom = dy2 * dx1 - dy1 * dx2; + + double nume_a = dx2 * (begin_.y_ - other_line.begin_.y_) - + dy2 * (begin_.x_ - other_line.begin_.x_); + + double nume_b = dx1 * (begin_.y_ - other_line.begin_.y_) - + dy1 * (begin_.x_ - other_line.begin_.x_); + + if(denom == 0.0f) + { + if(nume_a == 0.0f && nume_b == 0.0f) + { + return COINCIDENT; + } + return PARALLEL; + } + + double ua = nume_a / denom; + double ub = nume_b / denom; + + if(ua >= 0.0f && ua <= 1.0f && ub >= 0.0f && ub <= 1.0f) + { + // Get the intersection point. + intersection.x_ = begin_.x_ + ua*dx1; + intersection.y_ = begin_.y_ + ua*dy1; + + return INTERSECTING; + } + + return NOT_INTERSECTING; + } +}; + +void DoLineSegmentIntersection(const Vector& p0, const Vector& p1, const Vector& p2, const Vector& p3) +{ + LineSegment linesegment0(p0, p1); + LineSegment linesegment1(p2, p3); + + Vector intersection; + + std::cout << "Line Segment 0: (" << p0.x_ << ", " << p0.y_ << ") to (" << p1.x_ << ", " << p1.y_ << ")\n" + << "Line Segment 1: (" << p2.x_ << ", " << p2.y_ << ") to (" << p3.x_ << ", " << p3.y_ << ")\n"; + + switch(linesegment0.Intersect(linesegment1, intersection)) + { + case LineSegment::PARALLEL: + std::cout << "The lines are parallel\n\n"; + break; + case LineSegment::COINCIDENT: + std::cout << "The lines are coincident\n\n"; + break; + case LineSegment::NOT_INTERSECTING: + std::cout << "The lines do not intersect\n\n"; + break; + case LineSegment::INTERSECTING: + std::cout << "The lines intersect at (" << intersection.x_ << ", " << intersection.y_ << ")\n\n"; + break; + } +} + +int test() +{ + DoLineSegmentIntersection(Vector(0.0f, 0.0f), Vector(5.0f, 5.0f), Vector(5.0f, 0.0f), Vector(0.0f, 5.0f)); + DoLineSegmentIntersection(Vector(1.0f, 3.0f), Vector(9.0f, 3.0f), Vector(0.0f, 1.0f), Vector(2.0f, 1.0f)); + DoLineSegmentIntersection(Vector(1.0f, 5.0f), Vector(6.0f, 8.0f), Vector(0.5f, 3.0f), Vector(6.0f, 4.0f)); + DoLineSegmentIntersection(Vector(1.0f, 1.0f), Vector(3.0f, 8.0f), Vector(0.5f, 2.0f), Vector(4.0f, 7.0f)); + DoLineSegmentIntersection(Vector(1.0f, 2.0f), Vector(3.0f, 6.0f), Vector(2.0f, 4.0f), Vector(4.0f, 8.0f)); + DoLineSegmentIntersection(Vector(3.5f, 9.0f), Vector(3.5f, 0.5f), Vector(3.0f, 1.0f), Vector(9.0f, 1.0f)); + DoLineSegmentIntersection(Vector(2.0f, 3.0f), Vector(7.0f, 9.0f), Vector(1.0f, 2.0f), Vector(5.0f, 7.0f)); + return 0; +} +} // namespace linesegment + +#endif // VPSC_LINESEGMENT_H diff --git a/src/libvpsc/pairing_heap.h b/src/libvpsc/pairing_heap.h new file mode 100644 index 000000000..6e6457c07 --- /dev/null +++ b/src/libvpsc/pairing_heap.h @@ -0,0 +1,394 @@ +/* + * 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 Mark Allen Weiss + * Copyright (C) 2005-2008 Monash University + * + * ---------------------------------------------------------------------------- + * Pairing heap datastructure implementation: + * Based on example code in "Data structures and Algorithm Analysis in C++" + * by Mark Allen Weiss, used and released under the LGPL by permission + * of the author. + * No promises about correctness. Use at your own risk! + * ---------------------------------------------------------------------------- + * + * 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): Mark Allen Weiss + * Tim Dwyer +*/ + +#ifndef VPSC_PAIRING_HEAP_H +#define VPSC_PAIRING_HEAP_H + +#include <cstdlib> +#include <fstream> +#include <vector> +#include <list> + +#include "libvpsc/assertions.h" + +class Underflow { }; + +// Pairing heap class +// +// CONSTRUCTION: with no parameters +// +// ******************PUBLIC OPERATIONS********************* +// PairNode & insert( x ) --> Insert x +// deleteMin( minItem ) --> Remove (and optionally return) smallest item +// T findMin( ) --> Return smallest item +// bool isEmpty( ) --> Return true if empty; else false +// void makeEmpty( ) --> Remove all items +// void decreaseKey( PairNode p, newVal ) +// --> Decrease value in node p +// ******************ERRORS******************************** +// Throws Underflow as warranted + + +template <class T> +struct PairNode +{ + T element; + PairNode *leftChild; + PairNode *nextSibling; + PairNode *prev; + + PairNode( const T & theElement ) : + element( theElement ), + leftChild(NULL), nextSibling(NULL), prev(NULL) + { } +}; + +template <class T, class TCompare> +class PairingHeap; + +template <class T,class TCompare> +std::ostream& operator <<(std::ostream &os, const PairingHeap<T,TCompare> &b); + +template <class T, class TCompare = std::less<T> > +class PairingHeap +{ +#ifndef SWIG + friend std::ostream& operator<< <T,TCompare> (std::ostream &os, const PairingHeap<T,TCompare> &b); +#endif +public: + PairingHeap() : root(NULL), counter(0), siblingsTreeArray(5) { } + PairingHeap(const PairingHeap & rhs) { + // uses operator= to make deep copy + *this = rhs; + } + ~PairingHeap() { makeEmpty(); } + const PairingHeap & operator=( const PairingHeap & rhs ); + bool isEmpty() const { return root == NULL; } + unsigned size() const { return counter; } + PairNode<T> *insert( const T & x ); + const T & findMin( ) const; + void deleteMin( ); + const T extractMin( ) { + T v = findMin(); + deleteMin(); + return v; + } + void makeEmpty() { + reclaimMemory(root); + root = NULL; + counter = 0; + } + void decreaseKey( PairNode<T> *p, const T & newVal ); + void merge( PairingHeap<T,TCompare> *rhs ); +protected: + // Destructively gets the root for merging into another heap. + PairNode<T> * removeRootForMerge(unsigned& size) { + PairNode<T> *r=root; + root=NULL; + size=counter; + counter=0; + return r; + } + TCompare lessThan; +private: + PairNode<T> *root; + unsigned counter; + + // Used by PairingHeap::combineSiblings(). We keep this as member + // variable to save some vector resize operations during subsequent uses. + std::vector<PairNode<T> *> siblingsTreeArray; + + void reclaimMemory( PairNode<T> *t ) const; + void compareAndLink( PairNode<T> * & first, PairNode<T> *second ) const; + PairNode<T> * combineSiblings( PairNode<T> *firstSibling ); + PairNode<T> * clone( PairNode<T> * t ) const; +}; + + +/** +* Insert item x into the priority queue, maintaining heap order. +* Return a pointer to the node containing the new item. +*/ +template <class T,class TCompare> +PairNode<T> * +PairingHeap<T,TCompare>::insert( const T & x ) +{ + PairNode<T> *newNode = new PairNode<T>( x ); + + if( root == NULL ) + root = newNode; + else + compareAndLink( root, newNode ); + counter++; + return newNode; +} + +/** +* Find the smallest item in the priority queue. +* Return the smallest item, or throw Underflow if empty. +*/ +template <class T,class TCompare> +const T & PairingHeap<T,TCompare>::findMin( ) const +{ + if( isEmpty( ) ) + throw Underflow( ); + return root->element; +} +/** + * Remove the smallest item from the priority queue. + * Throws Underflow if empty. + */ +template <class T,class TCompare> +void PairingHeap<T,TCompare>::deleteMin( ) +{ + if( isEmpty( ) ) + throw Underflow( ); + + PairNode<T> *oldRoot = root; + + if( root->leftChild == NULL ) + root = NULL; + else + root = combineSiblings( root->leftChild ); + COLA_ASSERT(counter); + counter--; + delete oldRoot; +} + +/** +* Deep copy. +*/ +template <class T,class TCompare> +const PairingHeap<T,TCompare> & +PairingHeap<T,TCompare>::operator=( const PairingHeap<T,TCompare> & rhs ) +{ + if( this != &rhs ) + { + makeEmpty( ); + root = clone( rhs.root ); + counter = rhs.size(); + } + + return *this; +} + +/** +* Internal method to make the tree empty. +* WARNING: This is prone to running out of stack space. +*/ +template <class T,class TCompare> +void PairingHeap<T,TCompare>::reclaimMemory( PairNode<T> * t ) const +{ + if( t != NULL ) + { + reclaimMemory( t->leftChild ); + reclaimMemory( t->nextSibling ); + delete t; + } +} + +/** +* Change the value of the item stored in the pairing heap. +* Does nothing if newVal is larger than currently stored value. +* p points to a node returned by insert. +* newVal is the new value, which must be smaller +* than the currently stored value. +*/ +template <class T,class TCompare> +void PairingHeap<T,TCompare>::decreaseKey( PairNode<T> *p, + const T & newVal ) +{ + COLA_ASSERT(!lessThan(p->element,newVal)); // newVal cannot be bigger + p->element = newVal; + if( p != root ) + { + if( p->nextSibling != NULL ) + p->nextSibling->prev = p->prev; + if( p->prev->leftChild == p ) + p->prev->leftChild = p->nextSibling; + else + p->prev->nextSibling = p->nextSibling; + + p->nextSibling = NULL; + compareAndLink( root, p ); + } +} + +/** + * Merges rhs into this pairing heap by inserting its root + */ +template <class T,class TCompare> +void PairingHeap<T,TCompare>::merge( PairingHeap<T,TCompare> *rhs ) +{ + unsigned rhsSize; + PairNode<T> *broot=rhs->removeRootForMerge(rhsSize); + if (root == NULL) { + root = broot; + } else { + compareAndLink(root, broot); + } + counter+=rhsSize; +} + +/** +* Internal method that is the basic operation to maintain order. +* Links first and second together to satisfy heap order. +* first is root of tree 1, which may not be NULL. +* first->nextSibling MUST be NULL on entry. +* second is root of tree 2, which may be NULL. +* first becomes the result of the tree merge. +*/ +template <class T,class TCompare> +void PairingHeap<T,TCompare>:: +compareAndLink( PairNode<T> * & first, + PairNode<T> *second ) const +{ + if( second == NULL ) + return; + + if( lessThan(second->element,first->element) ) + { + // Attach first as leftmost child of second + second->prev = first->prev; + first->prev = second; + first->nextSibling = second->leftChild; + if( first->nextSibling != NULL ) + first->nextSibling->prev = first; + second->leftChild = first; + first = second; + } + else + { + // Attach second as leftmost child of first + second->prev = first; + first->nextSibling = second->nextSibling; + if( first->nextSibling != NULL ) + first->nextSibling->prev = first; + second->nextSibling = first->leftChild; + if( second->nextSibling != NULL ) + second->nextSibling->prev = second; + first->leftChild = second; + } +} + +/** +* Internal method that implements two-pass merging. +* firstSibling the root of the conglomerate; +* assumed not NULL. +*/ +template <class T,class TCompare> +PairNode<T> * +PairingHeap<T,TCompare>::combineSiblings( PairNode<T> *firstSibling ) +{ + if( firstSibling->nextSibling == NULL ) + return firstSibling; + + // Store the subtrees in an array + int numSiblings = 0; + for( ; firstSibling != NULL; numSiblings++ ) + { + if( numSiblings == (int)siblingsTreeArray.size( ) ) + siblingsTreeArray.resize( numSiblings * 2 ); + siblingsTreeArray[ numSiblings ] = firstSibling; + firstSibling->prev->nextSibling = NULL; // break links + firstSibling = firstSibling->nextSibling; + } + if( numSiblings == (int)siblingsTreeArray.size( ) ) + siblingsTreeArray.resize( numSiblings + 1 ); + siblingsTreeArray[ numSiblings ] = NULL; + + // Combine subtrees two at a time, going left to right + int i = 0; + for( ; i + 1 < numSiblings; i += 2 ) + compareAndLink( siblingsTreeArray[ i ], siblingsTreeArray[ i + 1 ] ); + + int j = i - 2; + + // j has the result of last compareAndLink. + // If an odd number of trees, get the last one. + if( j == numSiblings - 3 ) + compareAndLink( siblingsTreeArray[ j ], siblingsTreeArray[ j + 2 ] ); + + // Now go right to left, merging last tree with + // next to last. The result becomes the new last. + for( ; j >= 2; j -= 2 ) + compareAndLink( siblingsTreeArray[ j - 2 ], siblingsTreeArray[ j ] ); + return siblingsTreeArray[ 0 ]; +} + +/** +* Internal method to clone subtree. +* WARNING: This is prone to running out of stack space. +*/ +template <class T,class TCompare> +PairNode<T> * +PairingHeap<T,TCompare>::clone( PairNode<T> * t ) const +{ + if( t == NULL ) + return NULL; + else + { + PairNode<T> *p = new PairNode<T>( t->element ); + if( ( p->leftChild = clone( t->leftChild ) ) != NULL ) + p->leftChild->prev = p; + if( ( p->nextSibling = clone( t->nextSibling ) ) != NULL ) + p->nextSibling->prev = p; + return p; + } +} + +template <class T,class TCompare> +std::ostream& operator <<(std::ostream &os, const PairingHeap<T,TCompare> &b) +{ + os<<"Heap:"; + if (b.root != NULL) { + PairNode<T> *r = b.root; + std::list<PairNode<T>*> q; + q.push_back(r); + while (!q.empty()) { + r = q.front(); + q.pop_front(); + if (r->leftChild != NULL) { + os << *r->element << ">"; + PairNode<T> *c = r->leftChild; + while (c != NULL) { + q.push_back(c); + os << "," << *c->element; + c = c->nextSibling; + } + os << "|"; + } + } + } + return os; +} + +#endif /* VPSC_PAIRING_HEAP_H */ diff --git a/src/libvpsc/pairingheap/PairingHeap.cpp b/src/libvpsc/pairingheap/PairingHeap.cpp deleted file mode 100644 index 6e003f99c..000000000 --- a/src/libvpsc/pairingheap/PairingHeap.cpp +++ /dev/null @@ -1,335 +0,0 @@ -/** - * @file - * Pairing heap datastructure implementation. - * - * Based on example code in "Data structures and Algorithm Analysis in C++" - * by Mark Allen Weiss, used and released under the LGPL by permission - * of the author. - * - * No promises about correctness. Use at your own risk! - */ -/* - * Authors: - * Mark Allen Weiss - * Tim Dwyer <tgdwyer@gmail.com> - * - * Copyright (C) 2005 Authors - * - * Released under GNU LGPL. Read the file 'COPYING' for more information. - */ - -#include <vector> -#include <list> -#include "dsexceptions.h" -#include "PairingHeap.h" - -#ifndef PAIRING_HEAP_CPP -#define PAIRING_HEAP_CPP -using namespace std; -/** -* Construct the pairing heap. -*/ -template <class T> -PairingHeap<T>::PairingHeap( bool (*lessThan)(T const &lhs, T const &rhs) ) -{ - root = NULL; - counter=0; - this->lessThan=lessThan; -} - - -/** -* Copy constructor -*/ -template <class T> -PairingHeap<T>::PairingHeap( const PairingHeap<T> & rhs ) -{ - root = NULL; - counter=rhs->size(); - *this = rhs; -} - -/** -* Destroy the leftist heap. -*/ -template <class T> -PairingHeap<T>::~PairingHeap( ) -{ - makeEmpty( ); -} - -/** -* Insert item x into the priority queue, maintaining heap order. -* Return a pointer to the node containing the new item. -*/ -template <class T> -PairNode<T> * -PairingHeap<T>::insert( const T & x ) -{ - PairNode<T> *newNode = new PairNode<T>( x ); - - if( root == NULL ) - root = newNode; - else - compareAndLink( root, newNode ); - counter++; - return newNode; -} -template <class T> -int PairingHeap<T>::size() { - return counter; -} -/** -* Find the smallest item in the priority queue. -* Return the smallest item, or throw Underflow if empty. -*/ -template <class T> -const T & PairingHeap<T>::findMin( ) const -{ - if( isEmpty( ) ) - throw Underflow( ); - return root->element; -} -/** - * Remove the smallest item from the priority queue. - * Throws Underflow if empty. - */ -template <class T> -void PairingHeap<T>::deleteMin( ) -{ - if( isEmpty( ) ) - throw Underflow( ); - - PairNode<T> *oldRoot = root; - - if( root->leftChild == NULL ) - root = NULL; - else - root = combineSiblings( root->leftChild ); - counter--; - delete oldRoot; -} - -/** -* Test if the priority queue is logically empty. -* Returns true if empty, false otherwise. -*/ -template <class T> -bool PairingHeap<T>::isEmpty( ) const -{ - return root == NULL; -} - -/** -* Test if the priority queue is logically full. -* Returns false in this implementation. -*/ -template <class T> -bool PairingHeap<T>::isFull( ) const -{ - return false; -} - -/** -* Make the priority queue logically empty. -*/ -template <class T> -void PairingHeap<T>::makeEmpty( ) -{ - reclaimMemory( root ); - root = NULL; -} - -/** -* Deep copy. -*/ -template <class T> -const PairingHeap<T> & -PairingHeap<T>::operator=( const PairingHeap<T> & rhs ) -{ - if( this != &rhs ) - { - makeEmpty( ); - root = clone( rhs.root ); - } - - return *this; -} - -/** -* Internal method to make the tree empty. -* WARNING: This is prone to running out of stack space. -*/ -template <class T> -void PairingHeap<T>::reclaimMemory( PairNode<T> * t ) const -{ - if( t != NULL ) - { - reclaimMemory( t->leftChild ); - reclaimMemory( t->nextSibling ); - delete t; - } -} - -/** -* Change the value of the item stored in the pairing heap. -* Does nothing if newVal is larger than currently stored value. -* p points to a node returned by insert. -* newVal is the new value, which must be smaller -* than the currently stored value. -*/ -template <class T> -void PairingHeap<T>::decreaseKey( PairNode<T> *p, - const T & newVal ) -{ - if( lessThan(p->element,newVal) ) - return; // newVal cannot be bigger - p->element = newVal; - if( p != root ) - { - if( p->nextSibling != NULL ) - p->nextSibling->prev = p->prev; - if( p->prev->leftChild == p ) - p->prev->leftChild = p->nextSibling; - else - p->prev->nextSibling = p->nextSibling; - - p->nextSibling = NULL; - compareAndLink( root, p ); - } -} - -/** -* Internal method that is the basic operation to maintain order. -* Links first and second together to satisfy heap order. -* first is root of tree 1, which may not be NULL. -* first->nextSibling MUST be NULL on entry. -* second is root of tree 2, which may be NULL. -* first becomes the result of the tree merge. -*/ -template <class T> -void PairingHeap<T>:: -compareAndLink( PairNode<T> * & first, - PairNode<T> *second ) const -{ - if( second == NULL ) - return; - if( lessThan(second->element,first->element) ) - { - // Attach first as leftmost child of second - second->prev = first->prev; - first->prev = second; - first->nextSibling = second->leftChild; - if( first->nextSibling != NULL ) - first->nextSibling->prev = first; - second->leftChild = first; - first = second; - } - else - { - // Attach second as leftmost child of first - second->prev = first; - first->nextSibling = second->nextSibling; - if( first->nextSibling != NULL ) - first->nextSibling->prev = first; - second->nextSibling = first->leftChild; - if( second->nextSibling != NULL ) - second->nextSibling->prev = second; - first->leftChild = second; - } -} - -/** -* Internal method that implements two-pass merging. -* firstSibling the root of the conglomerate; -* assumed not NULL. -*/ -template <class T> -PairNode<T> * -PairingHeap<T>::combineSiblings( PairNode<T> *firstSibling ) const -{ - if( firstSibling->nextSibling == NULL ) - return firstSibling; - - // Allocate the array - static vector<PairNode<T> *> treeArray( 5 ); - - // Store the subtrees in an array - int numSiblings = 0; - for( ; firstSibling != NULL; numSiblings++ ) - { - if( numSiblings == (int)treeArray.size( ) ) - treeArray.resize( numSiblings * 2 ); - treeArray[ numSiblings ] = firstSibling; - firstSibling->prev->nextSibling = NULL; // break links - firstSibling = firstSibling->nextSibling; - } - if( numSiblings == (int)treeArray.size( ) ) - treeArray.resize( numSiblings + 1 ); - treeArray[ numSiblings ] = NULL; - - // Combine subtrees two at a time, going left to right - int i = 0; - for( ; i + 1 < numSiblings; i += 2 ) - compareAndLink( treeArray[ i ], treeArray[ i + 1 ] ); - - int j = i - 2; - - // j has the result of last compareAndLink. - // If an odd number of trees, get the last one. - if( j == numSiblings - 3 ) - compareAndLink( treeArray[ j ], treeArray[ j + 2 ] ); - - // Now go right to left, merging last tree with - // next to last. The result becomes the new last. - for( ; j >= 2; j -= 2 ) - compareAndLink( treeArray[ j - 2 ], treeArray[ j ] ); - return treeArray[ 0 ]; -} - -/** -* Internal method to clone subtree. -* WARNING: This is prone to running out of stack space. -*/ -template <class T> -PairNode<T> * -PairingHeap<T>::clone( PairNode<T> * t ) const -{ - if( t == NULL ) - return NULL; - else - { - PairNode<T> *p = new PairNode<T>( t->element ); - if( ( p->leftChild = clone( t->leftChild ) ) != NULL ) - p->leftChild->prev = p; - if( ( p->nextSibling = clone( t->nextSibling ) ) != NULL ) - p->nextSibling->prev = p; - return p; - } -} -template <class T> -ostream& operator <<(ostream &os, const PairingHeap<T> &b) -{ - os<<"Heap:"; - if (b.root != NULL) { - PairNode<T> *r = b.root; - list<PairNode<T>*> q; - q.push_back(r); - while (!q.empty()) { - r = q.front(); - q.pop_front(); - if (r->leftChild != NULL) { - os << *r->element << ">"; - PairNode<T> *c = r->leftChild; - while (c != NULL) { - q.push_back(c); - os << "," << *c->element; - c = c->nextSibling; - } - os << "|"; - } - } - } - return os; -} -#endif diff --git a/src/libvpsc/pairingheap/PairingHeap.h b/src/libvpsc/pairingheap/PairingHeap.h deleted file mode 100644 index 62c782d5d..000000000 --- a/src/libvpsc/pairingheap/PairingHeap.h +++ /dev/null @@ -1,125 +0,0 @@ -/* - * No promises about correctness. Use at your own risk! - * - * Authors: - * Mark Allen Weiss - * Tim Dwyer <tgdwyer@gmail.com> - * - * Copyright (C) 2005 Authors - * - * Released under GNU LGPL. Read the file 'COPYING' for more information. - */ -#ifndef PAIRING_HEAP_H_ -#define PAIRING_HEAP_H_ -#include <stdlib.h> -#include <fstream> -// Pairing heap class -// -// CONSTRUCTION: with no parameters -// -// ******************PUBLIC OPERATIONS********************* -// PairNode & insert( x ) --> Insert x -// deleteMin( minItem ) --> Remove (and optionally return) smallest item -// T findMin( ) --> Return smallest item -// bool isEmpty( ) --> Return true if empty; else false -// bool isFull( ) --> Return true if empty; else false -// void makeEmpty( ) --> Remove all items -// void decreaseKey( PairNode p, newVal ) -// --> Decrease value in node p -// ******************ERRORS******************************** -// Throws Underflow as warranted - - -// Node and forward declaration because g++ does -// not understand nested classes. -template <class T> -class PairingHeap; - -template <class T> -std::ostream& operator<< (std::ostream &os,const PairingHeap<T> &b); - -template <class T> -class PairNode -{ - friend std::ostream& operator<< <T>(std::ostream &os,const PairingHeap<T> &b); - T element; - PairNode *leftChild; - PairNode *nextSibling; - PairNode *prev; - - PairNode( const T & theElement ) : - element( theElement ), - leftChild(NULL), nextSibling(NULL), prev(NULL) - { } - friend class PairingHeap<T>; -}; - -template <class T> -class Comparator -{ -public: - virtual bool isLessThan(T const &lhs, T const &rhs) const = 0; -}; - -/** - * Pairing heap datastructure implementation. - * - * Based on example code in "Data structures and Algorithm Analysis in C++" - * by Mark Allen Weiss, used and released under the LGPL by permission - * of the author. - */ -template <class T> -class PairingHeap -{ - friend std::ostream& operator<< <T>(std::ostream &os,const PairingHeap<T> &b); -public: - PairingHeap( bool (*lessThan)(T const &lhs, T const &rhs) ); - PairingHeap( const PairingHeap & rhs ); - virtual ~PairingHeap( ); - - bool isEmpty( ) const; - bool isFull( ) const; - int size(); - - PairNode<T> *insert( const T & x ); - const T & findMin( ) const; - void deleteMin( ); - const T extractMin( ) { - T v = findMin(); - deleteMin(); - return v; - } - void makeEmpty( ); - void decreaseKey( PairNode<T> *p, const T & newVal ); - void merge( PairingHeap<T> *rhs ) - { - PairNode<T> *broot=rhs->getRoot(); - if (root == NULL) { - if(broot != NULL) { - root = broot; - } - } else { - compareAndLink(root, broot); - } - counter+=rhs->size(); - } - - const PairingHeap & operator=( const PairingHeap & rhs ); -protected: - PairNode<T> * getRoot() { - PairNode<T> *r=root; - root=NULL; - return r; - } -private: - PairNode<T> *root; - bool (*lessThan)(T const &lhs, T const &rhs); - int counter; - void reclaimMemory( PairNode<T> *t ) const; - void compareAndLink( PairNode<T> * & first, PairNode<T> *second ) const; - PairNode<T> * combineSiblings( PairNode<T> *firstSibling ) const; - PairNode<T> * clone( PairNode<T> * t ) const; -}; - -#include "PairingHeap.cpp" -#endif diff --git a/src/libvpsc/pairingheap/dsexceptions.h b/src/libvpsc/pairingheap/dsexceptions.h deleted file mode 100644 index bef2c78c5..000000000 --- a/src/libvpsc/pairingheap/dsexceptions.h +++ /dev/null @@ -1,9 +0,0 @@ -#ifndef DSEXCEPTIONS_H_ -#define DSEXCEPTIONS_H_ - -class Underflow { }; -class Overflow { }; -class OutOfMemory { }; -class BadIterator { }; - -#endif diff --git a/src/libvpsc/placement_SolveVPSC.h b/src/libvpsc/placement_SolveVPSC.h deleted file mode 100644 index 9f1c10cda..000000000 --- a/src/libvpsc/placement_SolveVPSC.h +++ /dev/null @@ -1,53 +0,0 @@ -/* DO NOT EDIT THIS FILE - it is machine generated */ -#include <jni.h> -/* Header for class placement_SolveVPSC */ - -#ifndef _Included_placement_SolveVPSC -#define _Included_placement_SolveVPSC -#ifdef __cplusplus -extern "C" { -#endif -/* - * Class: placement_SolveVPSC - * Method: solve - * Signature: ([Ljava/lang/String;[D[D[I[I[D[DI)D - */ -JNIEXPORT jdouble JNICALL Java_placement_SolveVPSC_solve - (JNIEnv *, jobject, jobjectArray, jdoubleArray, jdoubleArray, jintArray, jintArray, jdoubleArray, jdoubleArray, jint); - -/* - * Class: placement_SolveVPSC - * Method: generateXConstraints - * Signature: ([D[D[D[D[D)I - */ -JNIEXPORT jint JNICALL Java_placement_SolveVPSC_generateXConstraints - (JNIEnv *, jobject, jdoubleArray, jdoubleArray, jdoubleArray, jdoubleArray, jdoubleArray); - -/* - * Class: placement_SolveVPSC - * Method: generateYConstraints - * Signature: ([D[D[D[D[D)I - */ -JNIEXPORT jint JNICALL Java_placement_SolveVPSC_generateYConstraints - (JNIEnv *, jobject, jdoubleArray, jdoubleArray, jdoubleArray, jdoubleArray, jdoubleArray); - -/* - * Class: placement_SolveVPSC - * Method: getConstraints - * Signature: ([I[I[D)V - */ -JNIEXPORT void JNICALL Java_placement_SolveVPSC_getConstraints - (JNIEnv *, jobject, jintArray, jintArray, jdoubleArray); - -/* - * Class: placement_SolveVPSC - * Method: removeOverlaps - * Signature: ([D[D[D[D)V - */ -JNIEXPORT void JNICALL Java_placement_SolveVPSC_removeOverlaps - (JNIEnv *, jobject, jdoubleArray, jdoubleArray, jdoubleArray, jdoubleArray); - -#ifdef __cplusplus -} -#endif -#endif diff --git a/src/libvpsc/rectangle.cpp b/src/libvpsc/rectangle.cpp new file mode 100644 index 000000000..f040f4427 --- /dev/null +++ b/src/libvpsc/rectangle.cpp @@ -0,0 +1,745 @@ +/* + * 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 +*/ + +/* + * @brief Functions to automatically generate constraints for the + * rectangular node overlap removal problem. + * + */ + +#include <set> +#include <cstdlib> +#include <algorithm> +#include <cstdio> + +#include "libvpsc/assertions.h" +#include "libvpsc/solve_VPSC.h" +#include "libvpsc/rectangle.h" +#include "libvpsc/constraint.h" +#include "libvpsc/variable.h" + +#include "libvpsc/isnan.h" /* Include last */ + +using std::set; +using std::vector; + +namespace vpsc { + +double Rectangle::xBorder = 0; +double Rectangle::yBorder = 0; + +std::ostream& operator <<(std::ostream &os, const Rectangle &r) { + os << "Hue[0.17],Rectangle[{"<<r.getMinX()<<","<<r.getMinY()<<"},{"<<r.getMaxX()<<","<<r.getMaxY()<<"}]"; + return os; +} + +Rectangle::Rectangle(double x, double X, double y, double Y,bool allowOverlap) + : minX(x), + maxX(X), + minY(y), + maxY(Y), + overlap(allowOverlap) +{ + COLA_ASSERT(x<X); + COLA_ASSERT(y<Y); + COLA_ASSERT(getMinX()<getMaxX()); + COLA_ASSERT(getMinY()<getMaxY()); +} + +Rectangle::Rectangle() + : minX(1), + maxX(-1), + minY(1), + maxY(-1), + overlap(false) +{ + // Creates an invalid Rectangle +} + +bool Rectangle::isValid(void) const +{ + return ((minX <= maxX) && (minY <= maxY)); +} + +Rectangle Rectangle::unionWith(const Rectangle& rhs) const +{ + if (!isValid()) + { + return Rectangle(rhs); + } + else if (!rhs.isValid()) + { + return Rectangle(*this); + } + + double newMaxY = std::max(rhs.getMaxY(),maxY); + double newMinY = std::min(rhs.getMinY(),minY); + double newMinX = std::min(rhs.getMinX(),minX); + double newMaxX = std::max(rhs.getMaxX(),maxX); + + return Rectangle(newMinX, newMaxX, newMinY, newMaxY); +} + +void Rectangle::reset(unsigned d, double x, double X) { + if(d==0) { + minX=x; + maxX=X; + } else { + minY=x; + maxY=X; + } +} + +struct Node; +struct CmpNodePos { bool operator()(const Node* u, const Node* v) const; }; + +typedef set<Node*,CmpNodePos> NodeSet; + +struct Node { + Variable *v; + Rectangle *r; + double pos; + Node *firstAbove, *firstBelow; + NodeSet *leftNeighbours, *rightNeighbours; + Node(Variable *v, Rectangle *r, double p) + : v(v),r(r),pos(p), + firstAbove(NULL), firstBelow(NULL), + leftNeighbours(NULL), rightNeighbours(NULL) + + { + COLA_ASSERT(r->width()<1e40); + } + ~Node() { + delete leftNeighbours; + delete rightNeighbours; + } + void addLeftNeighbour(Node *u) { + COLA_ASSERT(leftNeighbours!=NULL); + leftNeighbours->insert(u); + } + void addRightNeighbour(Node *u) { + COLA_ASSERT(rightNeighbours!=NULL); + rightNeighbours->insert(u); + } + void setNeighbours(NodeSet *left, NodeSet *right) { + leftNeighbours=left; + rightNeighbours=right; + for(NodeSet::iterator i=left->begin();i!=left->end();++i) { + Node *v=*(i); + v->addRightNeighbour(this); + } + for(NodeSet::iterator i=right->begin();i!=right->end();++i) { + Node *v=*(i); + v->addLeftNeighbour(this); + } + } +}; +bool CmpNodePos::operator() (const Node* u, const Node* v) const { + COLA_ASSERT(!isNaN(u->pos)); + COLA_ASSERT(!isNaN(v->pos)); + if (u->pos < v->pos) { + return true; + } + if (v->pos < u->pos) { + return false; + } + return u < v; +} + +NodeSet* getLeftNeighbours(NodeSet &scanline,Node *v) { + NodeSet *leftv = new NodeSet; + NodeSet::iterator i=scanline.find(v); + while(i!=scanline.begin()) { + Node *u=*(--i); + if(u->r->overlapX(v->r)<=0) { + leftv->insert(u); + return leftv; + } + if(u->r->overlapX(v->r)<=u->r->overlapY(v->r)) { + leftv->insert(u); + } + } + return leftv; +} +NodeSet* getRightNeighbours(NodeSet &scanline,Node *v) { + NodeSet *rightv = new NodeSet; + NodeSet::iterator i=scanline.find(v); + for(++i;i!=scanline.end(); ++i) { + Node *u=*(i); + if(u->r->overlapX(v->r)<=0) { + rightv->insert(u); + return rightv; + } + if(u->r->overlapX(v->r)<=u->r->overlapY(v->r)) { + rightv->insert(u); + } + } + return rightv; +} + +typedef enum {Open, Close} EventType; +struct Event { + EventType type; + Node *v; + double pos; + Event(EventType t, Node *v, double p) : type(t),v(v),pos(p) {}; +}; +int compare_events(const void *a, const void *b) { + Event *ea=*(Event**)a; + Event *eb=*(Event**)b; + if(ea->pos==eb->pos) { + // when comparing opening and closing + // open must come first + if(ea->type==Open) return -1; + return 1; + } else if(ea->pos > eb->pos) { + return 1; + } else if(ea->pos < eb->pos) { + return -1; + } else if(isNaN(ea->pos) != isNaN(ea->pos)) { + /* See comment in CmpNodePos. */ + return ( isNaN(ea->pos) + ? -1 + : 1 ); + } + return 0; +} + +/* + * Prepares constraints in order to apply VPSC horizontally. Assumes + * variables have already been created. + * useNeighbourLists determines whether or not a heuristic is used to + * deciding whether to resolve all overlap in the x pass, or leave some + * overlaps for the y pass. + */ +void generateXConstraints(const Rectangles& rs, const Variables& vars, + Constraints& cs, const bool useNeighbourLists) +{ + const unsigned n = rs.size(); + COLA_ASSERT(vars.size()>=n); + Event **events=new Event*[2*n]; + unsigned i,ctr=0; + for(i=0;i<n;i++) { + vars[i]->desiredPosition=rs[i]->getCentreX(); + Node *v = new Node(vars[i],rs[i],rs[i]->getCentreX()); + events[ctr++]=new Event(Open,v,rs[i]->getMinY()); + events[ctr++]=new Event(Close,v,rs[i]->getMaxY()); + } + qsort((Event*)events, (size_t)2*n, sizeof(Event*), compare_events ); + + NodeSet scanline; + for(i=0;i<2*n;i++) { + Event *e=events[i]; + Node *v=e->v; + if(e->type==Open) { + scanline.insert(v); + if(useNeighbourLists) { + v->setNeighbours( + getLeftNeighbours(scanline,v), + getRightNeighbours(scanline,v) + ); + } else { + NodeSet::iterator it=scanline.find(v); + if(it!=scanline.begin()) { + Node *u=*(--it); + v->firstAbove=u; + u->firstBelow=v; + } + it=scanline.find(v); + if(++it!=scanline.end()) { + Node *u=*it; + v->firstBelow=u; + u->firstAbove=v; + } + } + } else { + size_t result; + // Close event + if(useNeighbourLists) { + for(NodeSet::iterator i=v->leftNeighbours->begin(); + i!=v->leftNeighbours->end();i++ + ) { + Node *u=*i; + double sep = (v->r->width()+u->r->width())/2.0; + cs.push_back(new Constraint(u->v,v->v,sep)); + result=u->rightNeighbours->erase(v); + COLA_ASSERT(result==1); + } + + for(NodeSet::iterator i=v->rightNeighbours->begin(); + i!=v->rightNeighbours->end();i++ + ) { + Node *u=*i; + double sep = (v->r->width()+u->r->width())/2.0; + cs.push_back(new Constraint(v->v,u->v,sep)); + result=u->leftNeighbours->erase(v); + COLA_ASSERT(result==1); + } + } else { + Node *l=v->firstAbove, *r=v->firstBelow; + if(l!=NULL) { + double sep = (v->r->width()+l->r->width())/2.0; + cs.push_back(new Constraint(l->v,v->v,sep)); + l->firstBelow=v->firstBelow; + } + if(r!=NULL) { + double sep = (v->r->width()+r->r->width())/2.0; + cs.push_back(new Constraint(v->v,r->v,sep)); + r->firstAbove=v->firstAbove; + } + } + result=scanline.erase(v); + COLA_ASSERT(result==1); + delete v; + } + delete e; + } + COLA_ASSERT(scanline.size()==0); + delete [] events; +} + +/* + * Prepares constraints in order to apply VPSC vertically to remove ALL + * overlap. + */ +void generateYConstraints(const Rectangles& rs, const Variables& vars, + Constraints& cs) +{ + const unsigned n = rs.size(); + COLA_ASSERT(vars.size()>=n); + Event **events=new Event*[2*n]; + unsigned ctr=0; + Rectangles::const_iterator ri=rs.begin(), re=rs.end(); + Variables::const_iterator vi=vars.begin(), ve=vars.end(); + for(;ri!=re&&vi!=ve;++ri,++vi) { + Rectangle* r=*ri; + Variable* v=*vi; + v->desiredPosition=r->getCentreY(); + Node *node = new Node(v,r,r->getCentreY()); + COLA_ASSERT(r->getMinX()<r->getMaxX()); + events[ctr++]=new Event(Open,node,r->getMinX()); + events[ctr++]=new Event(Close,node,r->getMaxX()); + } + COLA_ASSERT(ri==rs.end()); + qsort((Event*)events, (size_t)2*n, sizeof(Event*), compare_events ); + NodeSet scanline; +#ifndef NDEBUG + size_t deletes=0; +#endif + for(unsigned i=0;i<2*n;i++) { + Event *e=events[i]; + Node *v=e->v; + if(e->type==Open) { + scanline.insert(v); + NodeSet::iterator it=scanline.find(v); + if(it!=scanline.begin()) { + Node *u=*(--it); + v->firstAbove=u; + u->firstBelow=v; + } + it=scanline.find(v); + if(++it!=scanline.end()) { + Node *u=*it; + v->firstBelow=u; + u->firstAbove=v; + } + } else { + // Close event + Node *l=v->firstAbove, *r=v->firstBelow; + if(l!=NULL) { + double sep = (v->r->height()+l->r->height())/2.0; + cs.push_back(new Constraint(l->v,v->v,sep)); + l->firstBelow=v->firstBelow; + } + if(r!=NULL) { + double sep = (v->r->height()+r->r->height())/2.0; + cs.push_back(new Constraint(v->v,r->v,sep)); + r->firstAbove=v->firstAbove; + } +#ifndef NDEBUG + deletes++; + size_t erased= +#endif + scanline.erase(v); + COLA_ASSERT(erased==1); + delete v; + } + delete e; + } + COLA_ASSERT(scanline.size()==0); + COLA_ASSERT(deletes==n); + delete [] events; +} +#include "libvpsc/linesegment.h" +using namespace linesegment; +inline bool checkIntersection( + const LineSegment::IntersectResult result, + Vector const &intersection, + RectangleIntersections &ri, + bool &side, double &sideX, double &sideY) { + switch(result) { + case LineSegment::INTERSECTING: + ri.intersects=side=true; + sideX=intersection.x_; + sideY=intersection.y_; + case LineSegment::PARALLEL: + case LineSegment::NOT_INTERSECTING: + return true; + case LineSegment::COINCIDENT: + ri.intersects=ri.top=ri.bottom=ri.left=ri.right=false; + return false; + } + return false; +} +void Rectangle:: +lineIntersections(double x1, double y1, double x2, double y2, RectangleIntersections &ri) const { + Vector intersection; + LineSegment l(Vector(x1,y1),Vector(x2,y2)); + LineSegment top(Vector(getMinX(),getMaxY()),Vector(getMaxX(),getMaxY())); + if(!checkIntersection( + l.Intersect(top,intersection),intersection, + ri,ri.top,ri.topX,ri.topY)) { + return; + } + LineSegment bottom(Vector(getMinX(),getMinY()),Vector(getMaxX(),getMinY())); + if(!checkIntersection( + l.Intersect(bottom,intersection),intersection, + ri,ri.bottom,ri.bottomX,ri.bottomY)) { + return; + } + LineSegment left(Vector(getMinX(),getMinY()),Vector(getMinX(),getMaxY())); + if(!checkIntersection( + l.Intersect(left,intersection),intersection, + ri,ri.left,ri.leftX,ri.leftY)) { + return; + } + LineSegment right(Vector(getMaxX(),getMinY()),Vector(getMaxX(),getMaxY())); + if(!checkIntersection( + l.Intersect(right,intersection),intersection, + ri,ri.right,ri.rightX,ri.rightY)) { + return; + } +} +static const double ERROR_MARGIN = 1e-4; +inline bool eq(double a, double b) { + return fabs(a-b)<ERROR_MARGIN; + //return a==b; +} +/* +bool Rectangle::inside(double x, double y) const { + return x>(minX+ERROR_MARGIN) && x<(maxX-ERROR_MARGIN) + && y>(minY+ERROR_MARGIN) && y<(maxY-ERROR_MARGIN); +} +*/ +// p1=(x1,y1),p2=(x2,y2) are points on the boundary. Puts the shortest +// path round the outside of the rectangle from p1 to p2 into xs, ys. +void Rectangle::routeAround(double x1, double y1, double x2, double y2, + std::vector<double> &xs, std::vector<double> &ys) { + COLA_ASSERT(eq(x1,minX) || eq(x1,maxX) || eq(y1,minY) || eq(y1,maxY)); + COLA_ASSERT(eq(x2,minX) || eq(x2,maxX) || eq(y2,minY) || eq(y2,maxY)); + xs.push_back(x1); + ys.push_back(y1); + bool top1=eq(y1,maxY), top2=eq(y2,maxY), + bottom1=eq(y1,minY), bottom2=eq(y2,minY); + bool left1=eq(x1,minX), left2=eq(x2,minX), + right1=eq(x1,maxX), right2=eq(x2,maxX); + bool leftright = (left1 && right2) || (right1 && left2); + bool topbottom = (top1 && bottom2) || (bottom1 && top2); + bool lefttop = (left1 && top2) || (top1 && left2); + bool righttop = (right1 && top2) || (top1 && right2); + bool leftbottom = (left1 && bottom2) || (bottom1 && left2); + bool rightbottom = (right1 && bottom2) || (bottom1 && right2); + if(lefttop) { + xs.push_back(minX); + ys.push_back(maxY); + } else if(righttop) { + xs.push_back(maxX); + ys.push_back(maxY); + } else if(leftbottom) { + xs.push_back(minX); + ys.push_back(minY); + } else if(rightbottom) { + xs.push_back(maxX); + ys.push_back(minY); + } else if(leftright) { + double midY = y1+(y2-y1)/2.0; + if(left1) { // left to right + if(midY<getCentreY()) { // route below + // bottom left + xs.push_back(getMinX()); + ys.push_back(getMinY()); + // bottom right + xs.push_back(getMaxX()); + ys.push_back(getMinY()); + } else { // route above + // top left + xs.push_back(getMinX()); + ys.push_back(getMaxY()); + // top right + xs.push_back(getMaxX()); + ys.push_back(getMaxY()); + } + } else { // right to left + if(midY<getCentreY()) { // route below + // bottom right + xs.push_back(getMaxX()); + ys.push_back(getMinY()); + // bottom left + xs.push_back(getMinX()); + ys.push_back(getMinY()); + } else { // route above + // top right + xs.push_back(getMaxX()); + ys.push_back(getMaxY()); + // top left + xs.push_back(getMinX()); + ys.push_back(getMaxY()); + } + } + } else if(topbottom) { + double midX = x1+(x2-x1)/2.0; + if(top1) { + if(midX<getCentreX()) { // route left + // top left + xs.push_back(getMinX()); + ys.push_back(getMaxY()); + // bottom left + xs.push_back(getMinX()); + ys.push_back(getMinY()); + } else { // route right + // top right + xs.push_back(getMaxX()); + ys.push_back(getMaxY()); + // bottom right + xs.push_back(getMaxX()); + ys.push_back(getMinY()); + } + } else { // bottom to top + if(midX<getCentreX()) { // route left + // bottom left + xs.push_back(getMinX()); + ys.push_back(getMinY()); + // top left + xs.push_back(getMinX()); + ys.push_back(getMaxY()); + } else { // route right + // bottom right + xs.push_back(getMaxX()); + ys.push_back(getMinY()); + // top right + xs.push_back(getMaxX()); + ys.push_back(getMaxY()); + } + } + } + xs.push_back(x2); + ys.push_back(y2); +} + +/* + * moves all the rectangles to remove all overlaps. Heuristic + * attempts to move by as little as possible. + * no overlaps guaranteed. + * @param rs the rectangles which will be moved to remove overlap + */ +void removeoverlaps(Rectangles& rs) { + const set<unsigned> fixed; + removeoverlaps(rs,fixed); +} +#define ISNOTNAN(d) (d)==(d) +/* + * Moves rectangles to remove all overlaps. A heuristic + * attempts to move by as little as possible. The heuristic is + * that the overlaps are removed horizontally and then vertically, + * each pass being a quadratic program in which the total squared movement + * is minimised subject to non-overlap constraints. An optional third + * horizontal pass (in addition to the first horizontal pass and the second + * vertical pass) can be applied wherein the x-positions of rectangles are reset to their + * original positions and overlap removal repeated. This may avoid some + * unnecessary movement. + * @param rs the rectangles which will be moved to remove overlap + * @param fixed a set of indices to rectangles which should not be moved + * @param thirdPass optionally run the third horizontal pass described above. + */ +void removeoverlaps(Rectangles& rs, const set<unsigned>& fixed, bool thirdPass) { + const double xBorder=Rectangle::xBorder, yBorder=Rectangle::yBorder; + static const double EXTRA_GAP=1e-3; + static const size_t ARRAY_UNUSED=1; + unsigned n=rs.size(); + try { + // The extra gap avoids numerical imprecision problems + Rectangle::setXBorder(xBorder+EXTRA_GAP); + Rectangle::setYBorder(yBorder+EXTRA_GAP); + Variables vs(n); + Variables::iterator v; + unsigned i=0; + vector<double> initX(thirdPass?n:ARRAY_UNUSED); + for(v=vs.begin();v!=vs.end();++v,++i) { + double weight=1; + if(fixed.find(i)!=fixed.end()) { + weight=10000; + } + *v=new Variable(i,0,weight); + if(thirdPass) { + initX[i]=rs[i]->getCentreX(); + } + } + Constraints cs; + generateXConstraints(rs,vs,cs,true); + Solver vpsc_x(vs,cs); + vpsc_x.solve(); + Rectangles::iterator r=rs.begin(); + for(v=vs.begin();v!=vs.end();++v,++r) { + COLA_ASSERT(ISNOTNAN((*v)->finalPosition)); + (*r)->moveCentreX((*v)->finalPosition); + } + COLA_ASSERT(r==rs.end()); + for_each(cs.begin(),cs.end(),delete_object()); + cs.clear(); + // Removing the extra gap here ensures things that were moved to be + // adjacent to one another above are not considered overlapping + Rectangle::setXBorder(xBorder); + generateYConstraints(rs,vs,cs); + Solver vpsc_y(vs,cs); + vpsc_y.solve(); + r=rs.begin(); + for(v=vs.begin();v!=vs.end();++v,++r) { + COLA_ASSERT(ISNOTNAN((*v)->finalPosition)); + (*r)->moveCentreY((*v)->finalPosition); + } + for_each(cs.begin(),cs.end(),delete_object()); + cs.clear(); + Rectangle::setYBorder(yBorder); + if(thirdPass) { + // we reset x positions to their original values + // and apply a third pass horizontally so that + // rectangles which were moved unnecessarily in the + // first horizontal pass (i.e. their overlap + // was later resolved vertically) have an + // opportunity now to stay put. + Rectangle::setXBorder(xBorder+EXTRA_GAP); + r=rs.begin(); + for(v=vs.begin();v!=vs.end();++v,++r) { + (*r)->moveCentreX(initX[(*v)->id]); + } + generateXConstraints(rs,vs,cs,false); + Solver vpsc_x2(vs,cs); + vpsc_x2.solve(); + r=rs.begin(); + for(v=vs.begin();v!=vs.end();++v,++r) { + COLA_ASSERT(ISNOTNAN((*v)->finalPosition)); + (*r)->moveCentreX((*v)->finalPosition); + } + } + Rectangle::setXBorder(xBorder); + for_each(cs.begin(),cs.end(),delete_object()); + for_each(vs.begin(),vs.end(),delete_object()); + } catch (char *str) { + std::cerr<<str<<std::endl; + for(Rectangles::iterator r=rs.begin();r!=rs.end();++r) { + std::cerr << **r <<std::endl; + } + } + COLA_ASSERT(noRectangleOverlaps(rs)); +} + + +bool noRectangleOverlaps(const Rectangles& rs) +{ + Rectangle *u, *v; + Rectangles::const_iterator i=rs.begin(), j, e=rs.end(); + for (;i!=e;++i) + { + u=*i; + for (j=i+1;j!=e;++j) + { + v=*j; + if (u->overlapX(v)>0) + { + COLA_ASSERT(u->overlapY(v)==0); + } + } + } + return true; +} + +// checks if line segment is strictly overlapping. +// That is, if any point on the line is inside the rectangle. +bool Rectangle::overlaps(double x1, double y1, double x2, double y2) +{ + RectangleIntersections ri; + lineIntersections(x1,y1,x2,y2,ri); + if(ri.intersects) { + if(ri.countIntersections()==1) { + // special case when one point is touching + // the boundary of the rectangle but no part + // of the line is interior + if(!inside(x1,y1)&&!inside(x2,y2)) { + return false; + } + } + printf("Rectangle/Segment intersection (SVG):\n"); + printf("<svg style=\"stroke: black; fill: none;\">\n"); + printf("<polyline points=\"%f,%f %f,%f\" />\n",x1,y1,x2,y2); + printf("<rect x=\"%f\" y=\"%f\" width=\"%f\" height=\"%f\" />\n", + getMinX(),getMinY(),width(),height()); + printf("</svg>\n"); + ri.printIntersections(); + return true; + } + return false; +} + + +void RectangleIntersections::printIntersections() +{ + printf("intersections:\n"); + if(top) printf(" top=%d:(%f,%f)\n",top,topX,topY); + if(bottom) printf(" bottom=%d:(%f,%f)\n",bottom,bottomX,bottomY); + if(left) printf(" left=%d:(%f,%f)\n",left,leftX,leftY); + if(right) printf(" right=%d:(%f,%f)\n",right,rightX,rightY); +} + +// Of the stored intersections, this returns the one closest to the +// specified point +void RectangleIntersections::nearest(double x, double y, double &xi, double &yi) { + bool is[]={top, right, bottom, left}; + double xs[]={topX, rightX, bottomX, leftX}; + double ys[]={topY, rightY, bottomY, leftY}; + double dx, dy, l, minl = 999999999999999.0; + for(unsigned i=0;i<4;i++) + { + if(is[i]) + { + dx=xs[i]-x; + dy=ys[i]-y; + l=dx*dx + dy*dy; + if(l<minl) + { + minl=l; + xi=xs[i]; + yi=ys[i]; + } + } + } +} + +} diff --git a/src/libvpsc/rectangle.h b/src/libvpsc/rectangle.h new file mode 100644 index 000000000..df7639933 --- /dev/null +++ b/src/libvpsc/rectangle.h @@ -0,0 +1,302 @@ +/* + * 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-2010 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 +*/ + +/* + * Functions to automatically generate constraints for the + * rectangular node overlap removal problem. + * + */ +#ifndef VPSC_RECTANGLE_H +#define VPSC_RECTANGLE_H + +#include <iostream> +#include <vector> +#include <set> +#include <cassert> +#include <cmath> + +#include "libvpsc/assertions.h" + +namespace vpsc { + +//! @brief Indicates the x- or y-dimension. +enum Dim { + //! The x-dimension (0). + HORIZONTAL = 0, + //! The x-dimension (0). + XDIM = 0, + //! The y-dimension (1). + VERTICAL = 1, + //! The y-dimension (1). + YDIM = 1, + // The dimension is not set. + UNSET = 2 +}; + +inline Dim conjugate(Dim d) { + return static_cast<Dim>(!d); +} +/* records the positions and sides through which a particular line intersects with a rectangle + */ +struct RectangleIntersections { + bool intersects, top, bottom, left, right; + double topX, topY, bottomX, bottomY, leftX, leftY, rightX, rightY; + RectangleIntersections() + : intersects(false),top(false),bottom(false),left(false),right(false), + topX(0),topY(0),bottomX(0),bottomY(0),leftX(0),leftY(0),rightX(0),rightY(0) {} + int countIntersections() { + return left+right+top+bottom; + } + void printIntersections(void); + // Of the stored intersections, this returns the one closest to the + // specified point + void nearest(double x, double y, double & xi, double & yi); +}; + +/** + * @brief A rectangle represents a fixed-size shape in the diagram that may + * be moved to prevent overlaps and satisfy constraints. + */ +class Rectangle { +public: + /** + * @brief Constructs a rectangle by specifying the positions of all + * four sides. + * + * @param[in] x Minimum horizontal value. + * @param[in] X Maximum horizontal value. + * @param[in] y Minimum vertical value. + * @param[in] Y Maximum vertical value. + * @param[in] allowOverlap not used currently. + */ + Rectangle(double x, double X, double y, double Y, + bool allowOverlap = false); + Rectangle(Rectangle const &Other) + : minX(Other.minX) + , maxX(Other.maxX) + , minY(Other.minY) + , maxY(Other.maxY) + , overlap(Other.overlap) { } + Rectangle(); + bool isValid(void) const; + Rectangle unionWith(const Rectangle& rhs) const; + /* + * reset the dimensions in one axis + * @param d axis (0==X, 1==Y) + * @param x min value + * @param X max value + */ + void reset(const unsigned d, double x, double X); + double getMaxX() const { return maxX+xBorder; } + double getMaxY() const { return maxY+yBorder; } + double getMinX() const { return minX-xBorder; } + double getMinY() const { return minY-yBorder; } + /* + * @param d axis: 0=horizontal 1=vertical + */ + double getMinD(unsigned const d) const { + COLA_ASSERT(d==0||d==1); + return ( d == 0 ? getMinX() : getMinY() ); + } + /* + * @param d axis: 0=horizontal 1=vertical + */ + double getMaxD(unsigned const d) const { + COLA_ASSERT(d==0||d==1); + return ( d == 0 ? getMaxX() : getMaxY() ); + } + void setMinD(unsigned const d, const double val) + { if ( d == 0) { minX = val; } else { minY = val; } } + void setMaxD(unsigned const d, const double val) + { if ( d == 0) { maxX = val; } else { maxY = val; } } + double getCentreX() const { return getMinX()+width()/2.0; } + double getCentreY() const { return getMinY()+height()/2.0; } + /* + * @param d axis: 0=horizontal 1=vertical + */ + double getCentreD(unsigned const d) const { + COLA_ASSERT(d==0||d==1); + return getMinD(d)+length(d)/2.0; + } + double width() const { return getMaxX()-getMinX(); } + double height() const { return getMaxY()-getMinY(); } + /* + * @param d axis: 0=width 1=height + * @return width or height + */ + double length(unsigned const d) const { + COLA_ASSERT(d==0||d==1); + return ( d == 0 ? width() : height() ); + } + void set_width(double w) { maxX = minX + w - 2.0*xBorder; } + void set_height(double h) { maxY = minY + h - 2.0*yBorder; } + void moveCentreD(const unsigned d, double p) { + COLA_ASSERT(d==0||d==1); + if(d == 0) { moveCentreX(p); + } else { moveCentreY(p); } + } + void moveCentreX(double x) { + moveMinX(x-width()/2.0); + } + void moveCentreY(double y) { + moveMinY(y-height()/2.0); + } + void moveCentre(double x, double y) { + moveCentreX(x); + moveCentreY(y); + } + void moveMinX(double x) { + double w=width(); + minX=x+xBorder; + maxX=x+w-xBorder; + COLA_ASSERT(fabs(width()-w)<1e-9); + } + void moveMinY(double y) { + double h=height(); + maxY=y+h-yBorder; + minY=y+yBorder; + COLA_ASSERT(fabs(height()-h)<1e-9); + } + double overlapD(const unsigned d, Rectangle* r) { + if(d==0) { + return overlapX(r); + } else { + return overlapY(r); + } + } + double overlapX(Rectangle *r) const { + double ux=getCentreX(), vx=r->getCentreX(); + if (ux <= vx && r->getMinX() < getMaxX()) + return getMaxX() - r->getMinX(); + if (vx <= ux && getMinX() < r->getMaxX()) + return r->getMaxX() - getMinX(); + return 0; + } + double overlapY(Rectangle *r) const { + double uy=getCentreY(), vy=r->getCentreY(); + if (uy <= vy && r->getMinY() < getMaxY()) { + return getMaxY() - r->getMinY(); + } + if (vy <= uy && getMinY() < r->getMaxY()) { + return r->getMaxY() - getMinY(); + } + return 0; + } + bool allowOverlap() { + return overlap; + } + void offset(double dx, double dy) { + minX += dx; + maxX += dx; + minY += dy; + maxY += dy; + } + // returns the intersections between the line segment from (x1,y1) + // to (x2,y2) and this rectangle. Any intersections points with + // sides are reported, lines coincident with a side are considered not + // to intersect. + void lineIntersections(double x1, double y1, double x2, double y2, RectangleIntersections &ri) const; + bool inside(double x, double y) const { + return x>getMinX() && x<getMaxX() && y>getMinY() && y<getMaxY(); + } + // checks if line segment is strictly overlapping. + // That is, if any point on the line is inside the rectangle. + bool overlaps(double x1, double y1, double x2, double y2); + // p1=(x1,y1),p2=(x2,y2) are points on the boundary. Puts the shortest + // path round the outside of the rectangle from p1 to p2 into xs, ys. + void routeAround(double x1, double y1, double x2, double y2, + std::vector<double> &xs, std::vector<double> &ys); + /* + * xBorder and yBorder can be set to add a border to the boundary of the + * rectangle. In other words, the size of the rectangle returned by the + * getters (getMinX, getMaxX, etc) will be slightly larger than the + * internal representation. This is useful in situations where we need the + * size considered in one axis to be slightly different to that considered + * in the other axis for example, to avoid numerical precision problems in + * the axis-by-axis overlap removal process. + */ + static double xBorder,yBorder; + static void setXBorder(double x) {xBorder=x;} + static void setYBorder(double y) {yBorder=y;} + +private: + double minX,maxX,minY,maxY; + bool overlap; +}; + +//! @brief A vector of pointers to Rectangle objects. +typedef std::vector<Rectangle*> Rectangles; + +std::ostream& operator<<(std::ostream& os, vpsc::Rectangle const &r); + +class Variable; +typedef std::vector<Variable *> Variables; +class Constraint; +typedef std::vector<Constraint *> Constraints; + +void generateXConstraints(const Rectangles& rs, const Variables& vars, + Constraints& cs, const bool useNeighbourLists); +void generateYConstraints(const Rectangles& rs, const Variables& vars, + Constraints& cs); + +/** + * @brief Uses VPSC to remove overlaps between rectangles. + * + * Moves rectangles to remove all overlaps. Heuristic attempts to move + * shapes by as little as possible. + * + * @param[in,out] rs The rectangles which will be moved to remove overlap + */ +void removeoverlaps(Rectangles& rs); + +/** + * @brief Uses VPSC to remove overlaps between rectangles, excluding some + * that should not be moved. + * + * Moves rectangles to remove all overlaps. A heuristic attempts to move + * shapes by as little as possible. The heuristic is that the overlaps + * are removed horizontally and then vertically, each pass being a + * quadratic program in which the total squared movement is minimised + * subject to non-overlap constraints. + * + * An optional third horizontal pass (in addition to the first horizontal + * pass and the second vertical pass) can be applied wherein the + * x-positions of rectangles are reset to their original positions and + * overlap removal repeated. This may avoid some unnecessary movement. + * + * @param[in,out] rs The rectangles which will be moved to remove overlap + * @param[in] fixed A set of indices to rectangles which should not be moved. + * @param[in] thirdPass Optionally run the third horizontal pass described above. + */ +void removeoverlaps(Rectangles& rs, const std::set<unsigned>& fixed, + bool thirdPass = true); + +// Useful for assertions: +bool noRectangleOverlaps(const Rectangles& rs); + +struct delete_object +{ + template <typename T> + void operator()(T *ptr){ delete ptr;} +}; + +} // namespace vpsc +#endif // VPSC_RECTANGLE_H diff --git a/src/libvpsc/remove_rectangle_overlap.cpp b/src/libvpsc/remove_rectangle_overlap.cpp deleted file mode 100644 index d667ffb1e..000000000 --- a/src/libvpsc/remove_rectangle_overlap.cpp +++ /dev/null @@ -1,106 +0,0 @@ -/* - * remove overlaps between a set of rectangles. - * - * Authors: - * Tim Dwyer <tgdwyer@gmail.com> - * - * Copyright (C) 2005 Authors - * - * Released under GNU LGPL. Read the file 'COPYING' for more information. - */ - -#include <iostream> -#include <cassert> -#include "generate-constraints.h" -#include "solve_VPSC.h" -#include "variable.h" -#include "constraint.h" -#include "remove_rectangle_overlap.h" /* own include */ -#ifdef RECTANGLE_OVERLAP_LOGGING -#include <fstream> -#include "blocks.h" -using std::ios; -using std::ofstream; -using std::endl; -#endif - -#define EXTRA_GAP 0.0001 -using namespace vpsc; - -double Rectangle::xBorder=0; -double Rectangle::yBorder=0; - -void removeRectangleOverlap(unsigned n, Rectangle *rs[], double xBorder, double yBorder) { - try { - // The extra gap avoids numerical imprecision problems - Rectangle::setXBorder(xBorder+EXTRA_GAP); - Rectangle::setYBorder(yBorder+EXTRA_GAP); - Variable **vs=new Variable*[n]; - for(unsigned i=0;i<n;i++) { - vs[i]=new Variable(i,0,1); - } - Constraint **cs; - double *oldX = new double[n]; - unsigned m=generateXConstraints(n,rs,vs,cs,true); - for(unsigned i=0;i<n;i++) { - oldX[i]=vs[i]->desiredPosition; - } - Solver vpsc_x(n,vs,m,cs); -#ifdef RECTANGLE_OVERLAP_LOGGING - ofstream f(LOGFILE,ios::app); - f<<"Calling VPSC: Horizontal pass 1"<<endl; - f.close(); -#endif - vpsc_x.solve(); - for(unsigned i=0;i<n;i++) { - rs[i]->moveCentreX(vs[i]->position()); - } - for(unsigned i = 0; i < m; ++i) { - delete cs[i]; - } - delete [] cs; - // Removing the extra gap here ensures things that were moved to be adjacent to - // one another above are not considered overlapping - Rectangle::setXBorder(Rectangle::xBorder-EXTRA_GAP); - m=generateYConstraints(n,rs,vs,cs); - Solver vpsc_y(n,vs,m,cs); -#ifdef RECTANGLE_OVERLAP_LOGGING - f.open(LOGFILE,ios::app); - f<<"Calling VPSC: Vertical pass"<<endl; - f.close(); -#endif - vpsc_y.solve(); - for(unsigned i=0;i<n;i++) { - rs[i]->moveCentreY(vs[i]->position()); - rs[i]->moveCentreX(oldX[i]); - } - delete [] oldX; - for(unsigned i = 0; i < m; ++i) { - delete cs[i]; - } - delete [] cs; - Rectangle::setYBorder(Rectangle::yBorder-EXTRA_GAP); - m=generateXConstraints(n,rs,vs,cs,false); - Solver vpsc_x2(n,vs,m,cs); -#ifdef RECTANGLE_OVERLAP_LOGGING - f.open(LOGFILE,ios::app); - f<<"Calling VPSC: Horizontal pass 2"<<endl; - f.close(); -#endif - vpsc_x2.solve(); - for(unsigned i = 0; i < m; ++i) { - delete cs[i]; - } - delete [] cs; - for(unsigned i=0;i<n;i++) { - rs[i]->moveCentreX(vs[i]->position()); - delete vs[i]; - } - delete [] vs; - } catch (char const *str) { - std::cerr<<str<<std::endl; - for(unsigned i=0;i<n;i++) { - std::cerr << *rs[i]<<std::endl; - } - } -} diff --git a/src/libvpsc/remove_rectangle_overlap.h b/src/libvpsc/remove_rectangle_overlap.h deleted file mode 100644 index 3e2f4cc8f..000000000 --- a/src/libvpsc/remove_rectangle_overlap.h +++ /dev/null @@ -1,34 +0,0 @@ -/* - * Declaration of main internal remove-overlaps function. - */ -/* Authors: - * Tim Dwyer <tgdwyer@gmail.com> - * - * Copyright (C) 2005 Authors - * - * Released under GNU LGPL. Read the file 'COPYING' for more information. - */ - -#ifndef REMOVE_RECTANGLE_OVERLAP_H_SEEN -#define REMOVE_RECTANGLE_OVERLAP_H_SEEN - -namespace vpsc { - class Rectangle; -} - -/** - * Takes an array of n rectangles and moves them as little as possible - * such that rectangles are separated by at least xBorder horizontally - * and yBorder vertically - * - * Works in three passes: - * 1) removes some overlap horizontally - * 2) removes remaining overlap vertically - * 3) a last horizontal pass removes all overlap starting from original - * x-positions - this corrects the case where rectangles were moved - * too much in the first pass. - */ -void removeRectangleOverlap(unsigned n, vpsc::Rectangle *rs[], double xBorder, double yBorder); - - -#endif /* !REMOVE_RECTANGLE_OVERLAP_H_SEEN */ diff --git a/src/libvpsc/solve_VPSC.cpp b/src/libvpsc/solve_VPSC.cpp index 83cb517b6..aebd0b8d8 100644 --- a/src/libvpsc/solve_VPSC.cpp +++ b/src/libvpsc/solve_VPSC.cpp @@ -1,387 +1,561 @@ /* - * Solve an instance of the "Variable Placement with Separation - * Constraints" problem. + * vim: ts=4 sw=4 et tw=0 wm=0 * - * Authors: - * Tim Dwyer <tgdwyer@gmail.com> + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. * - * Copyright (C) 2005 Authors + * Copyright (C) 2005-2008 Monash University * - * Released under GNU LGPL. Read the file 'COPYING' for more information. - */ + * 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 <cassert> -#include "constraint.h" -#include "block.h" -#include "blocks.h" -#include "solve_VPSC.h" -#include <math.h> +#include <cmath> #include <sstream> -#ifdef RECTANGLE_OVERLAP_LOGGING +#include <map> +#include <cfloat> +#include <set> + +#include "libvpsc/constraint.h" +#include "libvpsc/block.h" +#include "libvpsc/blocks.h" +#include "libvpsc/solve_VPSC.h" +#include "libvpsc/cbuffer.h" +#include "libvpsc/variable.h" +#include "libvpsc/assertions.h" +#include "libvpsc/exceptions.h" + +#ifdef LIBVPSC_LOGGING #include <fstream> #endif -#include <map> using namespace std; namespace vpsc { -static const double ZERO_UPPERBOUND=-0.0000001; +static const double ZERO_UPPERBOUND=-1e-10; +static const double LAGRANGIAN_TOLERANCE=-1e-4; -IncSolver::IncSolver(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]) - : Solver(n,vs,m,cs) { - inactive.assign(cs,cs+m); - for(ConstraintList::iterator i=inactive.begin();i!=inactive.end();++i) { - (*i)->active=false; - } +IncSolver::IncSolver(Variables const &vs, Constraints const &cs) + : Solver(vs,cs) +{ + inactive=cs; + for(Constraints::iterator i=inactive.begin();i!=inactive.end();++i) { + (*i)->active=false; + } } -Solver::Solver(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]) : m(m), cs(cs), n(n), vs(vs) { - bs=new Blocks(n, vs); -#ifdef RECTANGLE_OVERLAP_LOGGING - printBlocks(); - //assert(!constraintGraphIsCyclic(n,vs)); +Solver::Solver(Variables const &vs, Constraints const &cs) + : m(cs.size()), + cs(cs), + n(vs.size()), + vs(vs), + needsScaling(false) +{ + for(unsigned i=0;i<n;++i) { + vs[i]->in.clear(); + vs[i]->out.clear(); + + // Set needsScaling if any variables have a scale other than 1. + needsScaling |= (vs[i]->scale != 1); + } + for(unsigned i=0;i<m;++i) { + Constraint *c=cs[i]; + c->left->out.push_back(c); + c->right->in.push_back(c); + c->needsScaling = needsScaling; + } + bs=new Blocks(vs); +#ifdef LIBVPSC_LOGGING + printBlocks(); + //COLA_ASSERT(!constraintGraphIsCyclic(n,vs)); #endif } Solver::~Solver() { - delete bs; + delete bs; +} + +void IncSolver::addConstraint(Constraint *c) +{ + ++m; + c->active = false; + inactive.push_back(c); + c->left->out.push_back(c); + c->right->in.push_back(c); + c->needsScaling = needsScaling; } // useful in debugging void Solver::printBlocks() { -#ifdef RECTANGLE_OVERLAP_LOGGING - ofstream f(LOGFILE,ios::app); - for(set<Block*>::iterator i=bs->begin();i!=bs->end();++i) { - Block *b=*i; - f<<" "<<*b<<endl; - } - for(unsigned i=0;i<m;i++) { - f<<" "<<*cs[i]<<endl; - } +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + for(set<Block*>::iterator i=bs->begin();i!=bs->end();++i) { + Block *b=*i; + f<<" "<<*b<<endl; + } + for(unsigned i=0;i<m;i++) { + f<<" "<<*cs[i]<<endl; + } #endif } -void Solver::satisfy() { - list<Variable*> *vs=bs->totalOrder(); - for(list<Variable*>::iterator i=vs->begin();i!=vs->end();++i) { - Variable *v=*i; - if(!v->block->deleted) { - bs->mergeLeft(v->block); - } - } - bs->cleanup(); - for(unsigned i=0;i<m;i++) { - if(cs[i]->slack() < ZERO_UPPERBOUND) { -#ifdef RECTANGLE_OVERLAP_LOGGING - ofstream f(LOGFILE,ios::app); - f<<"Error: Unsatisfied constraint: "<<*cs[i]<<endl; +/** + * Stores the relative positions of the variables in their finalPosition + * field. + */ +void Solver::copyResult() { + for(Variables::const_iterator i=vs.begin();i!=vs.end();++i) { + Variable* v=*i; + v->finalPosition=v->position(); + COLA_ASSERT(v->finalPosition==v->finalPosition); + } +} +/** +* Produces a feasible - though not necessarily optimal - solution by +* examining blocks in the partial order defined by the directed acyclic +* graph of constraints. For each block (when processing left to right) we +* maintain the invariant that all constraints to the left of the block +* (incoming constraints) are satisfied. This is done by repeatedly merging +* blocks into bigger blocks across violated constraints (most violated +* first) fixing the position of variables inside blocks relative to one +* another so that constraints internal to the block are satisfied. +*/ +bool Solver::satisfy() { + list<Variable*> *vList=bs->totalOrder(); + for(list<Variable*>::iterator i=vList->begin();i!=vList->end();++i) { + Variable *v=*i; + if(!v->block->deleted) { + bs->mergeLeft(v->block); + } + } + bs->cleanup(); + bool activeConstraints=false; + for(unsigned i=0;i<m;i++) { + if(cs[i]->active) activeConstraints=true; + if(cs[i]->slack() < ZERO_UPPERBOUND) { +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"Error: Unsatisfied constraint: "<<*cs[i]<<endl; #endif - //assert(cs[i]->slack()>-0.0000001); - throw "Unsatisfied constraint"; - } - } - delete vs; + //COLA_ASSERT(cs[i]->slack()>-0.0000001); + throw UnsatisfiedConstraint(*cs[i]); + } + } + delete vList; + copyResult(); + return activeConstraints; } void Solver::refine() { - bool solved=false; - // Solve shouldn't loop indefinately - // ... but just to make sure we limit the number of iterations - unsigned maxtries=100; - while(!solved&&maxtries>0) { - solved=true; - maxtries--; - for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();++i) { - Block *b=*i; - b->setUpInConstraints(); - b->setUpOutConstraints(); - } - for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();++i) { - Block *b=*i; - Constraint *c=b->findMinLM(); - if(c!=NULL && c->lm<0) { -#ifdef RECTANGLE_OVERLAP_LOGGING - ofstream f(LOGFILE,ios::app); - f<<"Split on constraint: "<<*c<<endl; + bool solved=false; + // Solve shouldn't loop indefinately + // ... but just to make sure we limit the number of iterations + unsigned maxtries=100; + while(!solved&&maxtries>0) { + solved=true; + maxtries--; + size_t length = bs->size(); + for (size_t i = 0; i < length; ++i) + { + Block *b = bs->at(i); + b->setUpInConstraints(); + b->setUpOutConstraints(); + } + for (size_t i = 0; i < length; ++i) + { + Block *b = bs->at(i); + Constraint *c=b->findMinLM(); + if(c!=NULL && c->lm<LAGRANGIAN_TOLERANCE) { +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"Split on constraint: "<<*c<<endl; #endif - // Split on c - Block *l=NULL, *r=NULL; - bs->split(b,l,r,c); - bs->cleanup(); - // split alters the block set so we have to restart - solved=false; - break; - } - } - } - for(unsigned i=0;i<m;i++) { - if(cs[i]->slack() < ZERO_UPPERBOUND) { - assert(cs[i]->slack()>ZERO_UPPERBOUND); - throw "Unsatisfied constraint"; - } - } + // Split on c + Block *l=NULL, *r=NULL; + bs->split(b,l,r,c); + bs->cleanup(); + // split alters the block set so we have to restart + solved=false; + break; + } + } + } + for(unsigned i=0;i<m;i++) { + if(cs[i]->slack() < ZERO_UPPERBOUND) { + COLA_ASSERT(cs[i]->slack()>ZERO_UPPERBOUND); + throw UnsatisfiedConstraint(*cs[i]); + } + } } - -void Solver::solve() { - satisfy(); - refine(); +/** + * Calculate the optimal solution. After using satisfy() to produce a + * feasible solution, refine() examines each block to see if further + * refinement is possible by splitting the block. This is done repeatedly + * until no further improvement is possible. + */ +bool Solver::solve() { + satisfy(); + refine(); + copyResult(); + return bs->size()!=n; } -void IncSolver::solve() { -#ifdef RECTANGLE_OVERLAP_LOGGING - ofstream f(LOGFILE,ios::app); - f<<"solve_inc()..."<<endl; +bool IncSolver::solve() { +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"solve_inc()..."<<endl; #endif - double lastcost,cost = bs->cost(); - do { - lastcost=cost; - satisfy(); - splitBlocks(); - cost = bs->cost(); -#ifdef RECTANGLE_OVERLAP_LOGGING - f<<" cost="<<cost<<endl; + satisfy(); + double lastcost = DBL_MAX, cost = bs->cost(); + while(fabs(lastcost-cost)>0.0001) { + satisfy(); + lastcost=cost; + cost = bs->cost(); +#ifdef LIBVPSC_LOGGING + f<<" bs->size="<<bs->size()<<", cost="<<cost<<endl; #endif - } while(fabs(lastcost-cost)>0.0001); + } + copyResult(); + return bs->size()!=n; } - -void IncSolver::satisfy() { -#ifdef RECTANGLE_OVERLAP_LOGGING - ofstream f(LOGFILE,ios::app); - f<<"satisfy_inc()..."<<endl; +/** + * incremental version of satisfy that allows refinement after blocks are + * moved. + * + * - move blocks to new positions + * - repeatedly merge across most violated constraint until no more + * violated constraints exist + * + * Note: there is a special case to handle when the most violated constraint + * is between two variables in the same block. Then, we must split the block + * over an active constraint between the two variables. We choose the + * constraint with the most negative lagrangian multiplier. + */ +bool IncSolver::satisfy() { +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"satisfy_inc()..."<<endl; +#endif + splitBlocks(); + //long splitCtr = 0; + Constraint* v = NULL; + //CBuffer buffer(inactive); + while ( (v = mostViolated(inactive)) && + (v->equality || ((v->slack() < ZERO_UPPERBOUND) && !v->active)) ) + { + COLA_ASSERT(!v->active); + Block *lb = v->left->block, *rb = v->right->block; + if(lb != rb) { + lb->merge(rb,v); + } else { + if(lb->isActiveDirectedPathBetween(v->right,v->left)) { + // cycle found, relax the violated, cyclic constraint + v->unsatisfiable=true; + continue; + //UnsatisfiableException e; + //lb->getActiveDirectedPathBetween(e.path,v->right,v->left); + //e.path.push_back(v); + //throw e; + } + //if(splitCtr++>10000) { + //throw "Cycle Error!"; + //} + // constraint is within block, need to split first + try { + Constraint* splitConstraint + =lb->splitBetween(v->left,v->right,lb,rb); + if(splitConstraint!=NULL) { + COLA_ASSERT(!splitConstraint->active); + inactive.push_back(splitConstraint); + } else { + v->unsatisfiable=true; + continue; + } + } catch(UnsatisfiableException e) { + e.path.push_back(v); +#ifdef LIBVPSC_DEBUG + std::cerr << "Unsatisfiable:" << std::endl; + for(std::vector<Constraint*>::iterator r=e.path.begin(); + r!=e.path.end();++r) + { + std::cerr << **r <<std::endl; + } #endif - splitBlocks(); - long splitCtr = 0; - Constraint* v = NULL; - while((v=mostViolated(inactive))&&(v->equality || v->slack() < ZERO_UPPERBOUND)) { - assert(!v->active); - Block *lb = v->left->block, *rb = v->right->block; - if(lb != rb) { - lb->merge(rb,v); - } else { - if(lb->isActiveDirectedPathBetween(v->right,v->left)) { - // cycle found, relax the violated, cyclic constraint - v->gap = v->slack(); - continue; - } - if(splitCtr++>10000) { - throw "Cycle Error!"; - } - // constraint is within block, need to split first - inactive.push_back(lb->splitBetween(v->left,v->right,lb,rb)); - lb->merge(rb,v); - bs->insert(lb); - } - } -#ifdef RECTANGLE_OVERLAP_LOGGING - f<<" finished merges."<<endl; + v->unsatisfiable=true; + continue; + } + if(v->slack()>=0) { + COLA_ASSERT(!v->active); + // v was satisfied by the above split! + inactive.push_back(v); + bs->insert(lb); + bs->insert(rb); + } else { + bs->insert(lb->merge(rb,v)); + delete ((lb->deleted) ? lb : rb); + } + } +#ifdef LIBVPSC_LOGGING + f<<"...remaining blocks="<<bs->size()<<", cost="<<bs->cost()<<endl; #endif - bs->cleanup(); - for(unsigned i=0;i<m;i++) { - v=cs[i]; - if(v->slack() < ZERO_UPPERBOUND) { - ostringstream s; - s<<"Unsatisfied constraint: "<<*v; -#ifdef RECTANGLE_OVERLAP_LOGGING - ofstream f(LOGFILE,ios::app); - f<<s.str()<<endl; + } +#ifdef LIBVPSC_LOGGING + f<<" finished merges."<<endl; #endif - throw s.str().c_str(); - } - } -#ifdef RECTANGLE_OVERLAP_LOGGING - f<<" finished cleanup."<<endl; - printBlocks(); + bs->cleanup(); + bool activeConstraints=false; + for(unsigned i=0;i<m;i++) { + v=cs[i]; + if(v->active) activeConstraints=true; + if(v->slack() < ZERO_UPPERBOUND) { + ostringstream s; + s<<"Unsatisfied constraint: "<<*v; +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<s.str()<<endl; #endif + throw (char *) s.str().c_str(); + } + } +#ifdef LIBVPSC_LOGGING + f<<" finished cleanup."<<endl; + printBlocks(); +#endif + copyResult(); + return activeConstraints; } void IncSolver::moveBlocks() { -#ifdef RECTANGLE_OVERLAP_LOGGING - ofstream f(LOGFILE,ios::app); - f<<"moveBlocks()..."<<endl; +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"moveBlocks()..."<<endl; #endif - for(set<Block*>::const_iterator i(bs->begin());i!=bs->end();++i) { - Block *b = *i; - b->wposn = b->desiredWeightedPosition(); - b->posn = b->wposn / b->weight; - } -#ifdef RECTANGLE_OVERLAP_LOGGING - f<<" moved blocks."<<endl; + size_t length = bs->size(); + for (size_t i = 0; i < length; ++i) + { + Block *b = bs->at(i); + b->updateWeightedPosition(); + //b->posn = b->wposn / b->weight; + } +#ifdef LIBVPSC_LOGGING + f<<" moved blocks."<<endl; #endif } void IncSolver::splitBlocks() { -#ifdef RECTANGLE_OVERLAP_LOGGING - ofstream f(LOGFILE,ios::app); +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); #endif - moveBlocks(); - splitCnt=0; - // Split each block if necessary on min LM - for(set<Block*>::const_iterator i(bs->begin());i!=bs->end();++i) { - Block* b = *i; - Constraint* v=b->findMinLM(); - if(v!=NULL && v->lm < ZERO_UPPERBOUND) { - assert(!v->equality); -#ifdef RECTANGLE_OVERLAP_LOGGING - f<<" found split point: "<<*v<<" lm="<<v->lm<<endl; + moveBlocks(); + splitCnt=0; + // Split each block if necessary on min LM + size_t length = bs->size(); + for (size_t i = 0; i < length; ++i) + { + Block *b = bs->at(i); + Constraint* v=b->findMinLM(); + if(v!=NULL && v->lm < LAGRANGIAN_TOLERANCE) { + COLA_ASSERT(!v->equality); +#ifdef LIBVPSC_LOGGING + f<<" found split point: "<<*v<<" lm="<<v->lm<<endl; #endif - splitCnt++; - Block *b = v->left->block, *l=NULL, *r=NULL; - assert(v->left->block == v->right->block); - double pos = b->posn; - b->split(l,r,v); - l->posn=r->posn=pos; - l->wposn = l->posn * l->weight; - r->wposn = r->posn * r->weight; - bs->insert(l); - bs->insert(r); - b->deleted=true; - inactive.push_back(v); -#ifdef RECTANGLE_OVERLAP_LOGGING - f<<" new blocks: "<<*l<<" and "<<*r<<endl; + splitCnt++; + Block *b = v->left->block, *l=NULL, *r=NULL; + COLA_ASSERT(v->left->block == v->right->block); + //double pos = b->posn; + b->split(l,r,v); + //l->posn=r->posn=pos; + //l->wposn = l->posn * l->weight; + //r->wposn = r->posn * r->weight; + l->updateWeightedPosition(); + r->updateWeightedPosition(); + bs->insert(l); + bs->insert(r); + b->deleted=true; + COLA_ASSERT(!v->active); + inactive.push_back(v); +#ifdef LIBVPSC_LOGGING + f<<" new blocks: "<<*l<<" and "<<*r<<endl; #endif - } - } -#ifdef RECTANGLE_OVERLAP_LOGGING - f<<" finished splits."<<endl; + } + } + //if(splitCnt>0) { std::cout<<" splits: "<<splitCnt<<endl; } +#ifdef LIBVPSC_LOGGING + f<<" finished splits."<<endl; #endif - bs->cleanup(); + bs->cleanup(); } -Constraint* IncSolver::mostViolated(ConstraintList &l) { - double minSlack = DBL_MAX; - Constraint* v=NULL; -#ifdef RECTANGLE_OVERLAP_LOGGING - ofstream f(LOGFILE,ios::app); - f<<"Looking for most violated..."<<endl; +/** + * Scan constraint list for the most violated constraint, or the first equality + * constraint + */ +Constraint* IncSolver::mostViolated(Constraints &l) +{ + double slackForMostViolated = DBL_MAX; + Constraint* mostViolated = NULL; +#ifdef LIBVPSC_LOGGING + ofstream f(LOGFILE,ios::app); + f << "Looking for most violated..." << endl; #endif - ConstraintList::iterator end = l.end(); - ConstraintList::iterator deletePoint = end; - for(ConstraintList::iterator i=l.begin();i!=end;++i) { - Constraint *c=*i; - double slack = c->slack(); - if(c->equality || slack < minSlack) { - minSlack=slack; - v=c; - deletePoint=i; - if(c->equality) break; - } - } - // Because the constraint list is not order dependent we just - // move the last element over the deletePoint and resize - // downwards. There is always at least 1 element in the - // vector because of search. - if(deletePoint != end && (minSlack<ZERO_UPPERBOUND||v->equality)) { - *deletePoint = l[l.size()-1]; - l.resize(l.size()-1); - } -#ifdef RECTANGLE_OVERLAP_LOGGING - f<<" most violated is: "<<*v<<endl; + size_t lSize = l.size(); + size_t deleteIndex = lSize; + Constraint *constraint = NULL; + double slack = 0; + for (size_t index = 0; index < lSize; ++index) + { + constraint = l[index]; + slack = constraint->slack(); + if (constraint->equality || slack < slackForMostViolated) + { + slackForMostViolated = slack; + mostViolated = constraint; + deleteIndex = index; + if (constraint->equality) + { + break; + } + } + } + // Because the constraint list is not order dependent we just + // move the last element over the deletePoint and resize + // downwards. There is always at least 1 element in the + // vector because of search. + if ( (deleteIndex < lSize) && + (((slackForMostViolated < ZERO_UPPERBOUND) && !mostViolated->active) || + mostViolated->equality) ) + { + l[deleteIndex] = l[lSize-1]; + l.resize(lSize-1); + } +#ifdef LIBVPSC_LOGGING + if (mostViolated) + { + f << " most violated is: " << *mostViolated << endl; + } + else + { + f << " non found." << endl; + } #endif - return v; + return mostViolated; } struct node { - set<node*> in; - set<node*> out; + set<node*> in; + set<node*> out; }; // useful in debugging - cycles would be BAD bool Solver::constraintGraphIsCyclic(const unsigned n, Variable* const vs[]) { - map<Variable*, node*> varmap; - vector<node*> graph; - for(unsigned i=0;i<n;i++) { - node *u=new node; - graph.push_back(u); - varmap[vs[i]]=u; - } - for(unsigned i=0;i<n;i++) { - for(vector<Constraint*>::iterator c=vs[i]->in.begin();c!=vs[i]->in.end();++c) { - Variable *l=(*c)->left; - varmap[vs[i]]->in.insert(varmap[l]); - } + map<Variable*, node*> varmap; + vector<node*> graph; + for(unsigned i=0;i<n;i++) { + node *u=new node; + graph.push_back(u); + varmap[vs[i]]=u; + } + for(unsigned i=0;i<n;i++) { + for(vector<Constraint*>::iterator c=vs[i]->in.begin();c!=vs[i]->in.end();++c) { + Variable *l=(*c)->left; + varmap[vs[i]]->in.insert(varmap[l]); + } - for(vector<Constraint*>::iterator c=vs[i]->out.begin();c!=vs[i]->out.end();++c) { - Variable *r=(*c)->right; - varmap[vs[i]]->out.insert(varmap[r]); - } - } - while(!graph.empty()) { - node *u=NULL; - vector<node*>::iterator i=graph.begin(); - for(;i!=graph.end();++i) { - u=*i; - if(u->in.empty()) { - break; - } - } - if(i==graph.end() && !graph.empty()) { - //cycle found! - return true; - } else { - graph.erase(i); - for(set<node*>::iterator j=u->out.begin();j!=u->out.end();++j) { - node *v=*j; - v->in.erase(u); - } - delete u; - } - } - for(unsigned i=0; i<graph.size(); ++i) { - delete graph[i]; - } - return false; + for(vector<Constraint*>::iterator c=vs[i]->out.begin();c!=vs[i]->out.end();++c) { + Variable *r=(*c)->right; + varmap[vs[i]]->out.insert(varmap[r]); + } + } + while(graph.size()>0) { + node *u=NULL; + vector<node*>::iterator i=graph.begin(); + for(;i!=graph.end();++i) { + u=*i; + if(u->in.size()==0) { + break; + } + } + if(i==graph.end() && graph.size()>0) { + //cycle found! + return true; + } else { + graph.erase(i); + for(set<node*>::iterator j=u->out.begin();j!=u->out.end();++j) { + node *v=*j; + v->in.erase(u); + } + delete u; + } + } + for(unsigned i=0; i<graph.size(); ++i) { + delete graph[i]; + } + return false; } // useful in debugging - cycles would be BAD bool Solver::blockGraphIsCyclic() { - map<Block*, node*> bmap; - vector<node*> graph; - for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();++i) { - Block *b=*i; - node *u=new node; - graph.push_back(u); - bmap[b]=u; - } - for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();++i) { - Block *b=*i; - b->setUpInConstraints(); - Constraint *c=b->findMinInConstraint(); - while(c!=NULL) { - Block *l=c->left->block; - bmap[b]->in.insert(bmap[l]); - b->deleteMinInConstraint(); - c=b->findMinInConstraint(); - } + map<Block*, node*> bmap; + vector<node*> graph; + size_t length = bs->size(); + for (size_t i = 0; i < length; ++i) + { + Block *b = bs->at(i); + node *u=new node; + graph.push_back(u); + bmap[b]=u; + } + for (size_t i = 0; i < length; ++i) + { + Block *b = bs->at(i); + b->setUpInConstraints(); + Constraint *c=b->findMinInConstraint(); + while(c!=NULL) { + Block *l=c->left->block; + bmap[b]->in.insert(bmap[l]); + b->deleteMinInConstraint(); + c=b->findMinInConstraint(); + } - b->setUpOutConstraints(); - c=b->findMinOutConstraint(); - while(c!=NULL) { - Block *r=c->right->block; - bmap[b]->out.insert(bmap[r]); - b->deleteMinOutConstraint(); - c=b->findMinOutConstraint(); - } - } - while(!graph.empty()) { - node *u=NULL; - vector<node*>::iterator i=graph.begin(); - for(;i!=graph.end();++i) { - u=*i; - if(u->in.empty()) { - break; - } - } - if(i==graph.end() && !graph.empty()) { - //cycle found! - return true; - } else { - graph.erase(i); - for(set<node*>::iterator j=u->out.begin();j!=u->out.end();++j) { - node *v=*j; - v->in.erase(u); - } - delete u; - } - } - for(unsigned i=0; i<graph.size(); i++) { - delete graph[i]; - } - return false; + b->setUpOutConstraints(); + c=b->findMinOutConstraint(); + while(c!=NULL) { + Block *r=c->right->block; + bmap[b]->out.insert(bmap[r]); + b->deleteMinOutConstraint(); + c=b->findMinOutConstraint(); + } + } + while(graph.size()>0) { + node *u=NULL; + vector<node*>::iterator i=graph.begin(); + for(;i!=graph.end();++i) { + u=*i; + if(u->in.size()==0) { + break; + } + } + if(i==graph.end() && graph.size()>0) { + //cycle found! + return true; + } else { + graph.erase(i); + for(set<node*>::iterator j=u->out.begin();j!=u->out.end();++j) { + node *v=*j; + v->in.erase(u); + } + delete u; + } + } + for(unsigned i=0; i<graph.size(); i++) { + delete graph[i]; + } + return false; } } diff --git a/src/libvpsc/solve_VPSC.h b/src/libvpsc/solve_VPSC.h index e416ef9c6..5f7713c12 100644 --- a/src/libvpsc/solve_VPSC.h +++ b/src/libvpsc/solve_VPSC.h @@ -1,16 +1,24 @@ -/** - * @file - * Solve an instance of the "Variable Placement with Separation - * Constraints" problem. - */ /* - * Authors: - * Tim Dwyer <tgdwyer@gmail.com> + * vim: ts=4 sw=4 et tw=0 wm=0 * - * Copyright (C) 2005 Authors + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. * - * Released under GNU LGPL. Read the file 'COPYING' for more information. - */ + * Copyright (C) 2005-2013 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 +*/ // // TODO: Really, we should have three classes: VPSC, IncrementalVPSC and @@ -19,106 +27,104 @@ // Also, a lot of the code specific to one or other of these concrete // implementations should be moved from Block and Blocks: e.g. mergeLeft etc. // -#ifndef SEEN_REMOVEOVERLAP_SOLVE_VPSC_H -#define SEEN_REMOVEOVERLAP_SOLVE_VPSC_H +#ifndef VPSC_SOLVE_VPSC_H +#define VPSC_SOLVE_VPSC_H #include <vector> +/** + * @namespace vpsc + * @brief libvpsc: Variable Placement with Separation Constraints + * quadratic program solver library. + * + * You should use VPSC via an instance of the IncSolver or Solver classes. + */ namespace vpsc { class Variable; +typedef std::vector<Variable*> Variables; class Constraint; class Blocks; +typedef std::vector<Constraint*> Constraints; /** - * Variable Placement with Separation Constraints problem instance + * @brief Static solver for Variable Placement with Separation Constraints + * problem instance + * + * This class attempts to solve a least-squares problem subject to a set + * of separation constraints. The solve() and satisfy() methods return true + * if any constraints are active, in both cases false means an unconstrained + * optimum has been found. + * + * @sa IncSolver */ class Solver { public: - - /** - * Produces a feasible - though not necessarily optimal - solution by - * examining blocks in the partial order defined by the directed acyclic - * graph of constraints. For each block (when processing left to right) we - * maintain the invariant that all constraints to the left of the block - * (incoming constraints) are satisfied. This is done by repeatedly merging - * blocks into bigger blocks across violated constraints (most violated - * first) fixing the position of variables inside blocks relative to one - * another so that constraints internal to the block are satisfied. - */ - virtual void satisfy(); - - /** - * Calculate the optimal solution. After using satisfy() to produce a - * feasible solution, refine() examines each block to see if further - * refinement is possible by splitting the block. This is done repeatedly - * until no further improvement is possible. - */ - virtual void solve(); - - Solver(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]); + //! @brief Results in an approximate solution subject to the constraints. + //! @return true if any constraints are active, or false if an unconstrained + //! optimum has been found. + virtual bool satisfy(); + //! @brief Results in an optimum solution subject to the constraints + //! @return true if any constraints are active, or false if an unconstrained + //! optimum has been found. + virtual bool solve(); + + Solver(Variables const &vs, Constraints const &cs); virtual ~Solver(); - Constraint** getConstraints(unsigned &m) { m=this->m; return cs; } - const Variable* const * getVariables(unsigned &n) { n=this->n; return vs; } + //! @brief Returns the Variables in this problem instance. + //! @returns A vector of Variable objects. + Variables const & getVariables() { return vs; } protected: Blocks *bs; - unsigned m; - Constraint **cs; - unsigned n; - const Variable* const *vs; + size_t m; + std::vector<Constraint*> const &cs; + size_t n; + std::vector<Variable*> const &vs; + bool needsScaling; + void printBlocks(); + void copyResult(); private: void refine(); bool constraintGraphIsCyclic(const unsigned n, Variable* const vs[]); bool blockGraphIsCyclic(); }; +/** + * @brief Incremental solver for Variable Placement with Separation Constraints + * problem instance + * + * This class attempts to solve a least-squares problem subject to a set + * of sepation constraints. The solve() and satisfy() methods return true + * if any constraints are active, in both cases false means an unconstrained + * optimum has been found. This is an incremental version of that allows + * refinement after blocks are moved. This version is preferred if you are + * using VPSC in an interactive context. + * + * @sa Solver + */ class IncSolver : public Solver { public: - unsigned splitCnt; - - /** - * incremental version of satisfy that allows refinement after blocks are - * moved. - * - * - move blocks to new positions - * - repeatedly merge across most violated constraint until no more - * violated constraints exist - * - * Note: there is a special case to handle when the most violated constraint - * is between two variables in the same block. Then, we must split the block - * over an active constraint between the two variables. We choose the - * constraint with the most negative lagrangian multiplier. - */ - void satisfy(); - - void solve(); - - void moveBlocks(); - - void splitBlocks(); - - IncSolver(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]); + IncSolver(Variables const &vs, Constraints const &cs); + //! @brief Results in an approximate solution subject to the constraints. + //! @return true if any constraints are active, or false if an unconstrained + bool satisfy(); + //! @brief Results in an optimum solution subject to the constraints + //! @return true if any constraints are active, or false if an unconstrained + //! optimum has been found. + bool solve(); + //! @brief Adds a constraint to the existing VPSC solver. + //! + //! @param constraint The new additional constraint to add. + void addConstraint(Constraint *constraint); private: + void moveBlocks(); + void splitBlocks(); - typedef std::vector<Constraint*> ConstraintList; - - ConstraintList inactive; - - /** - * Scan constraint list for the most violated constraint, or the first equality - * constraint. - */ - Constraint* mostViolated(ConstraintList &l); + unsigned splitCnt; + Constraints inactive; + Constraints violated; + Constraint* mostViolated(Constraints &l); }; + } -#endif // SEEN_REMOVEOVERLAP_SOLVE_VPSC_H -/* - Local Variables: - mode:c++ - c-file-style:"stroustrup" - c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) - indent-tabs-mode:nil - fill-column:99 - End: -*/ -// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 : +#endif // VPSC_SOLVE_VPSC_H diff --git a/src/libvpsc/tests/Makefile.am b/src/libvpsc/tests/Makefile.am new file mode 100644 index 000000000..d155c5260 --- /dev/null +++ b/src/libvpsc/tests/Makefile.am @@ -0,0 +1,15 @@ +AM_CPPFLAGS = -I$(top_srcdir) + +check_PROGRAMS = rectangleoverlap block satisfy_inc # cycle +satisfy_inc_SOURCES = satisfy_inc.cpp +satisfy_inc_LDADD = $(top_builddir)/libvpsc/libvpsc.la # -L$(mosek_home)/bin -lmosek -lguide -limf -lirc +block_SOURCES = block.cpp +block_LDADD = $(top_builddir)/libvpsc/libvpsc.la +rectangleoverlap_SOURCES = rectangleoverlap.cpp +rectangleoverlap_LDADD = $(top_builddir)/libvpsc/libvpsc.la + +#cycle_SOURCES = cycle.cpp +#cycle_LDADD = $(top_builddir)/libvpsc/libvpsc.la + +TESTS = $(check_PROGRAMS) + diff --git a/src/libvpsc/tests/block.cpp b/src/libvpsc/tests/block.cpp new file mode 100644 index 000000000..08080e957 --- /dev/null +++ b/src/libvpsc/tests/block.cpp @@ -0,0 +1,105 @@ +/* + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library in the file LICENSE; if not, + * write to the Free Software Foundation, Inc., 59 Temple Place, + * Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#include <cassert> +#include <iostream> + +#include "libvpsc/variable.h" +#include "libvpsc/constraint.h" +#include "libvpsc/blocks.h" +#include "libvpsc/block.h" +using namespace std; +using namespace vpsc; + + +void test1() { + Blocks *blocks = new Blocks(Variables()); + cout << "Block test 1..." << endl; + Variable *a1=new Variable(1,0,1); + Variable *a2=new Variable(2,0,1); + Constraint *c=new Constraint(a1,a2,1); + a1->out.push_back(c); + a2->in.push_back(c); + Block *b1=new Block(blocks, a1); + Block *b2=new Block(blocks, a2); + b1->merge(b2,c); + cout << "Block: " << *b1 << endl; + a1->desiredPosition = -1; + a2->desiredPosition = 2; + Constraint *m = b1->findMinLMBetween(a1,a2); + cout << "Min lm constraint: " << *m << endl; + assert(c==m); + cout << " lm=" << c->lm << endl; + cout << "Block test 1... Success!" << endl; +} + +/* + * Constraint tree: + * \_/ + * / \ + */ +void test2() { + Blocks *blocks = new Blocks(Variables()); + cout << "Block test 2..." << endl; + Variable *a[]={ + new Variable(0,0,1), + new Variable(1,0,1), + new Variable(2,1,1), + new Variable(3,2,1), + new Variable(4,3,1), + new Variable(5,3,1)}; + Constraint *c[]={ + new Constraint(a[0],a[2],2), + new Constraint(a[1],a[2],2), + new Constraint(a[2],a[3],2), + new Constraint(a[3],a[4],2), + new Constraint(a[3],a[5],2)}; + for(int i=0;i<6;i++) { + new Block(blocks,a[i]); + } + for(int i=0;i<5;i++) { + c[i]->left->out.push_back(c[i]); + c[i]->right->in.push_back(c[i]); + } + for(int i=0;i<5;i++) { + Block *l=c[i]->left->block, *r=c[i]->right->block; + l->merge(r,c[i]); + } + Block *b=a[0]->block; + cout << "Block: " << *b << endl; + for(int i=0;i<6;i++) { + a[i]->desiredPosition = i!=4?-2:5; + } + cout << "calc min lm:" << endl; + Constraint *m = b->findMinLMBetween(a[0],a[4]); + cout << "Min lm constraint: " << *m << endl; + assert(m==c[3]); + cout << "Block test 2... Success!" << endl; +} +int main() { + test1(); + test2(); + return 0; +} diff --git a/src/libvpsc/tests/cycle.cpp b/src/libvpsc/tests/cycle.cpp new file mode 100644 index 000000000..26dda3a0c --- /dev/null +++ b/src/libvpsc/tests/cycle.cpp @@ -0,0 +1,106 @@ +/* + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library in the file LICENSE; if not, + * write to the Free Software Foundation, Inc., 59 Temple Place, + * Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#include <iostream> +#include <cassert> +#include <cmath> +#include <algorithm> +#include <libvpsc/rectangle.h> +#include <libvpsc/variable.h> +#include <libvpsc/constraint.h> +#include <libvpsc/solve_VPSC.h> +using namespace std; +using namespace vpsc; +inline bool approxEquals(const double a, const double b) { + return fabs((double)a-b)<0.0001; +} +void test1() { + cout << "Test 1..." << endl; + vector<Variable*> a; + a.push_back(new Variable(0,0,1)); + a.push_back(new Variable(1,1,1)); + vector<Constraint*> c; + c.push_back(new Constraint(a[0],a[1],2)); + c.push_back(new Constraint(a[1],a[0],2)); + double expected[]={1.5,-0.5}; + try { + IncSolver vpsc(a,c); + vpsc.solve(); + } catch (UnsatisfiableException& e) { + cerr << "Unsatisfiable" << endl; + for(vector<Constraint*>::iterator i=e.path.begin(); + i!=e.path.end();i++) { + cout << **i << endl; + } + exit(1); + } + //catch(...) { + //cerr << "Unknown error!" << endl; + //exit(1); + //} + + for(size_t i=0;i<a.size();i++) { + assert(approxEquals(a[i]->finalPosition,expected[i])); + } + for_each(a.begin(),a.end(),delete_object()); + for_each(c.begin(),c.end(),delete_object()); + cout << "Test 1... done." << endl; +} +void test2() { + cout << "Test 2..." << endl; + vector<Variable *> a; + a.push_back(new Variable(0,8,1)); + a.push_back(new Variable(1,5,1)); + a.push_back(new Variable(2,3,1)); + a.push_back(new Variable(3,1,1)); + vector<Constraint*> c; + c.push_back(new Constraint(a[0],a[3],3)); + c.push_back(new Constraint(a[0],a[1],3)); + c.push_back(new Constraint(a[1],a[3],3)); + c.push_back(new Constraint(a[1],a[2],3)); + c.push_back(new Constraint(a[2],a[3],3)); + c.push_back(new Constraint(a[2],a[3],3)); + //double expected[]={-3.71429,4,1,-0.714286,2.28571,2.28571,7,5.28571,8.28571,11.2857}; + try { + IncSolver vpsc(a,c); + vpsc.solve(); + } catch (char const *msg) { + cerr << msg << endl; + exit(1); + } + + /* + for(int i=0;i<n;i++) { + assert(approxEquals(a[i]->position(),expected[i])); + } + */ + cout << "Test 2... done." << endl; + for_each(a.begin(),a.end(),delete_object()); + for_each(c.begin(),c.end(),delete_object()); +} +int main() { + test1(); + return 0; +} diff --git a/src/libvpsc/tests/rectangleoverlap.cpp b/src/libvpsc/tests/rectangleoverlap.cpp new file mode 100644 index 000000000..d4fba2b1b --- /dev/null +++ b/src/libvpsc/tests/rectangleoverlap.cpp @@ -0,0 +1,660 @@ +/* + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library in the file LICENSE; if not, + * write to the Free Software Foundation, Inc., 59 Temple Place, + * Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#include <cstdio> +#include <cassert> +#include <cstdlib> +#include <math.h> +#include <time.h> +#include <libvpsc/rectangle.h> +#include <libvpsc/variable.h> +#include <libvpsc/constraint.h> +#include <libvpsc/solve_VPSC.h> +using namespace std; +using namespace vpsc; + +inline double getRand(double range) { + return range*rand()/RAND_MAX; +} +void printRects(vector<Rectangle*> &rs) { + printf("Set of %d rectangles:\n",(int)rs.size()); + for(unsigned i=0;i<rs.size();++i) { + cout << *rs[i] << endl; + } +} +void generateRandomRects(unsigned n, vector<Rectangle*> &rs) { + rs.resize(n); + static double const rect_size = 5; + static double const min_rect_size = 1e-4; + static double const fld_size = sqrt(rect_size * n / 2.0); + double coords[4]; + for (unsigned i = 0; i < n; ++i) { + for (unsigned d = 0; d < 2; ++d) { + //unsigned const end = 1 + (rand() % (fld_size - 1)); + //unsigned const start = rand() % end; + double const start = getRand(fld_size); + double const end = start + min_rect_size + + getRand(rect_size); + coords[2 * d] = start; + coords[2 * d + 1] = end; + } + rs[i]=new Rectangle(coords[0],coords[1],coords[2],coords[3]); + } +} +vector<Rectangle*>& generateRects(double coords[][4], unsigned n,vector<Rectangle *>& rs) { + rs.resize(n); + for (unsigned i = 0; i < n; ++i) { + rs[i]=new Rectangle(coords[i][0],coords[i][1],coords[i][2],coords[i][3]); + } + return rs; +} +void test(vector<Rectangle *> &rs, double &cost, double &duration) { + unsigned n=rs.size(); + vector<Rectangle *> ors(n); + for (unsigned i = 0; i < n; ++i) { + ors[i]=new Rectangle(rs[i]->getMinX(),rs[i]->getMaxX(),rs[i]->getMinY(),rs[i]->getMaxY()); + } + + clock_t starttime = clock(); + removeoverlaps(rs); + duration = (double)(clock() - starttime)/CLOCKS_PER_SEC; + cost = 0; + for(unsigned i=0;i<n;i++) { + double dx=rs[i]->getCentreX()-ors[i]->getCentreX(); + double dy=rs[i]->getCentreY()-ors[i]->getCentreY(); + cost+=sqrt(dx*dx+dy*dy); + delete rs[i]; + delete ors[i]; + } +} +double test1[][4]={ { 0, 50, 0, 30 }, { 10, 20, 10, 29 }, +{ 30, 70, 39, 70 }, { 0, 90, 40, 50 }, { 30, 70, 1, 29 } }; +unsigned n1=5; +double test2[][4]={ { 7, 22, 39, 54 }, { 7, 33, 0, 59 }, +{ 3, 26, 16, 56 }, { 7, 17, 18, 20 }, { 1, 59, 11, 26 }, +{ 19, 20, 13, 49 }, { 1, 10, 0, 4 }, { 47, 52, 1, 3 } }; +unsigned n2=8; +double test3[][4]={ { 8, 32, 29, 36 }, { 19, 24, 2, 27 }, +{ 4, 5, 27, 55 }, { 6, 7, 13, 26 }, { 3, 39, 46, 62 }, +{ 6, 23, 2, 19 }, { 18, 39, 5, 23 }, { 35, 63, 42, 78 }, +{ 16, 18, 14, 72 }, { 12, 32, 10, 58 } }; +unsigned n3=10; +double test4[][4]={ { 315.755, 355.288, 353.595, 449.627 }, +{ 395.048, 395.635, 253.943, 362.228 }, +{ 254.439, 393.289, 278.708, 286.346 }, +{ 209.852, 370.831, 326.496, 507.255 }, +{ 271.947, 415.74, 362.228, 450.318 }, +{ 293.408, 405.197, 220.61, 244.119 }, +{ 276.482, 386.472, 286.346, 435.767 }, +{ 268.211, 436.23, 192.807, 220.61 }, +{ 378.008, 502.118, 358.437, 475.587 }, +{ 340.68, 472.597, 249.492, 335.448 } }; +unsigned n4=10; +double test5[][4]={ { 7, 22, 39, 54 }, { 7, 33, 0, 59 }, +{ 3, 26, 16, 56 }, { 7, 17, 18, 20 }, { 1, 59, 11, 26 }, +{ 19, 20, 13, 49 }, { 1, 10, 0, 4 }, { 47, 52, 1, 3 } }; +unsigned n5=8; +double test6[][4]={ { 40, 69, 63, 69 }, { 1, 5, 27, 64 }, +{ 34, 66, 20, 22 }, { 1, 24, 10, 25 }, { 1, 19, 9, 61 }, +{ 0, 56, 8, 70 }, { 33, 35, 13, 28 }, { 11, 31, 33, 35 }, +{ 12, 22, 3, 23 } }; +unsigned n6=9; +double test7[][4]={ { 341.594, 388.459, 373.491, 518.168 }, +{ 271.214, 324.782, 311.332, 409.166 }, +{ 293.848, 475.064, 305.194, 391.162 }, +{ 255.317, 447.738, 342.671, 489.923 }, +{ 228.375, 261.057, 206.422, 327.794 }, +{ 383.552, 462.834, 363.132, 412.843 }, +{ 288.859, 481.054, 351.895, 497.728 }, +{ 201.307, 368.511, 387.02, 394.95 }, +{ 257.961, 259.673, 386.503, 518.403 }, +{ 200.178, 275.606, 364.968, 466.787 } }; +unsigned n7=10; +double test8[][4]={{12.807,15.7566,14.9478,16.7924}, +{7.76228,11.6532,4.75249,4.75349}, +{7.84596,10.1387,15.465,16.7709}, +{1.80748,3.0357,5.9983,6.16279}, +{6.46447,7.47249,12.8694,13.4378}, +{14.0026,17.3342,5.10141,9.81088}, +{6.84223,6.85932,6.40395,9.21135}, +{7.63462,10.3552,6.78124,8.59953}, +{0.26429,2.80847,14.5724,17.7455}, +{14.7686,15.7148,3.46036,5.66776}, +{10.635,11.4893,12.5044,16.941}, +{6.32027,10.7117,14.2953,15.6276}, +{11.9942,13.1118,10.6893,11.4477}, +{11.9384,15.1357,2.20982,6.92982}, +{2.89395,4.29002,11.7058,16.2896}, +{9.44116,12.7547,9.75556,11.1811}, +{5.2475,8.00607,15.3652,17.026}, +{2.09541,3.76981,2.5526,3.16739}, +{3.14595,6.66351,10.3007,14.4881}, +{4.88109,9.38044,9.02416,10.2954}, +{7.55378,9.14715,13.9686,16.0468}, +{1.70299,5.42198,14.1913,14.2191}, +{14.4877,14.4897,6.14013,8.50074}, +{12.9909,14.5163,10.322,12.4457}, +{11.616,12.0848,3.7601,5.45419}, +{10.3087,13.358,3.04666,3.53389}, +{2.28263,2.44881,13.806,15.8206}, +{3.31805,5.47662,3.91187,6.85355}, +{0.484138,2.06164,3.57335,7.87753}, +{4.73784,5.12359,9.383,11.9217}, +{12.2921,12.7769,12.329,12.8139}, +{12.7351,16.7141,12.7658,13.78}, +{3.71614,5.79872,1.53137,4.97126}, +{10.7423,14.8183,2.57104,2.94168}, +{9.93995,10.1557,1.3432,1.499}, +{0.198099,0.204966,9.29459,11.8795}, +{14.1043,18.8473,11.2028,14.1971}, +{4.23857,4.95743,14.7047,17.1439}, +{13.936,15.9612,10.7744,14.8598}, +{11.355,15.6824,2.49113,5.96963}, +{12.8528,16.3913,3.82582,6.67259}, +{13.9445,14.7354,10.8576,12.9503}, +{13.0041,15.6166,2.07035,3.70034}, +{2.31809,5.03195,1.13659,5.8604}, +{10.2454,14.5396,10.9442,15.4321}, +{7.12259,11.3929,7.20864,10.4059}, +{6.54862,9.88399,1.82828,5.89899}, +{4.27072,7.52613,7.99016,11.1703}, +{8.84828,9.15453,10.1489,11.7934}, +{7.71027,8.97206,3.26462,4.02636}, +{14.3383,15.1727,3.02586,3.26268}, +{9.21233,11.1919,13.9814,16.1433}, +{13.1946,16.1613,12.2268,13.1319}, +{13.0462,15.6689,7.03513,8.59752}, +{8.72724,11.3859,5.69193,7.8238}, +{10.6241,14.1033,7.88946,9.95327}, +{8.48376,10.8714,8.86955,11.2137}, +{3.55633,4.14351,13.7308,18.4988}, +{1.79802,4.68843,11.0964,11.6543}, +{13.1535,14.6895,1.52144,2.50643}, +{1.24533,4.27261,13.345,13.4925}, +{14.4031,18.7944,15.4447,18.0096}, +{8.56933,11.3392,0.446787,1.18762}, +{11.311,16.0574,8.41,8.76508}, +{13.5332,17.8479,8.2067,11.4446}, +{5.73826,6.63581,10.8364,11.6186}, +{10.1995,11.5202,6.54248,9.49804}, +{14.6456,16.7915,7.01621,7.57531}, +{15.1444,16.4184,1.45761,2.35577}, +{11.8169,12.0382,14.8149,19.3316}, +{10.148,11.1227,15.0087,18.1595}, +{10.9498,14.7849,12.3852,13.9467}, +{10.7631,10.9141,5.24419,8.64319}, +{11.2486,12.6029,6.25029,10.0076}, +{12.8731,16.0703,4.96619,8.54006}, +{6.92828,8.53172,8.36509,11.8971}, +{3.1677,7.20423,14.5582,17.1794}, +{14.1426,16.9327,15.1198,19.1306}, +{2.52943,6.64027,5.18935,8.58545}, +{6.89613,11.4515,3.7672,6.23813}, +{2.91428,6.40636,1.4231,4.10552}, +{9.81892,12.9687,8.25114,10.1775}, +{14.6192,14.7412,10.8349,15.1725}, +{6.96657,11.7009,11.0638,11.8966}, +{7.03182,9.20687,2.04293,2.60462}, +{7.47955,9.28533,7.45213,8.37318}, +{6.24651,9.79246,8.61803,9.91034}, +{4.73642,7.48461,9.59481,12.748}, +{8.70644,11.1702,2.54172,4.26587}, +{14.9028,19.4109,6.238,8.04256}, +{5.22907,8.45899,1.98714,4.94042}, +{8.96884,12.3636,1.72663,3.39844}, +{6.96563,8.04735,10.6198,11.3663}, +{1.65099,5.65883,10.5002,13.9039}, +{11.3337,11.5138,5.31369,7.75029}, +{2.79561,4.08151,7.04269,9.00167}}; + +unsigned n8=96; +double test9[][4]={{2.67865,4.81342,8.67025,11.5025}, +{5.77912,6.94355,9.80043,12.2904}, +{11.9459,13.8675,3.66967,7.38408}, +{6.72663,8.30474,3.37566,7.24571}, +{9.2081,10.9827,10.9557,11.8868}, +{0.161903,3.31202,3.35371,3.84933}, +{4.46508,9.18934,9.43037,10.9125}, +{3.84059,5.2565,8.66868,8.70713}, +{4.67598,5.15207,5.2252,8.92099}, +{1.19252,1.31215,7.97481,8.27191}, +{4.57641,5.71063,0.440628,4.17365}, +{6.80268,11.5523,3.78375,4.79819}, +{11.2172,13.7652,8.44876,11.1649}, +{11.4673,13.1644,6.09156,7.41026}, +{12.2995,13.585,0.155239,4.63887}, +{12.3513,15.3947,8.3437,11.1337}, +{3.92566,6.15611,12.432,16.3993}, +{12.6351,14.6039,9.96391,13.1152}, +{0.682894,2.48867,7.66904,8.86704}, +{3.50189,7.28939,8.37741,8.96276}, +{2.37719,4.19762,11.1129,12.0465}, +{5.53568,8.1444,11.9056,15.5818}, +{7.32876,11.2713,12.1655,15.0785}, +{2.534,6.15563,9.30845,11.2833}, +{8.00852,12.8051,2.16786,4.90262}, +{11.8095,12.814,11.5818,13.7731}, +{7.54398,9.23043,7.36953,10.7315}, +{8.36918,9.83071,11.8668,11.8776}, +{5.72267,9.66642,1.46379,3.71362}, +{11.2725,14.6538,4.76772,7.30304}, +{5.8638,10.7623,5.99865,10.0994}, +{11.0224,12.6455,0.852638,2.20201}, +{4.03151,8.51056,6.12449,10.3672}, +{7.75136,10.6782,10.648,11.8606}, +{11.9663,14.3993,2.83154,5.46437}, +{6.05275,8.00044,10.9675,15.3426}, +{10.9702,13.146,8.98465,12.4718}, +{4.99665,7.91376,9.19241,9.71153}, +{3.7422,4.00542,2.00556,2.53918}, +{9.01679,10.9439,12.8107,15.1367}, +{10.0117,11.5009,0.194049,3.08568}, +{8.29117,13.1323,6.99045,8.65707}, +{5.97395,10.5816,5.77559,7.35126}, +{5.68856,6.51699,4.40392,5.82242}, +{0.209729,3.89072,7.36013,8.98447}, +{0.360264,1.88558,0.319886,3.22738}, +{2.02163,2.07428,3.2753,8.12958}, +{5.05075,5.86987,12.7958,16.7689}, +{10.6484,15.5931,7.23546,10.4741}, +{7.20998,7.46939,2.44384,5.10459}, +{12.5022,15.1819,10.6593,13.5708}, +{2.3619,2.45407,5.75168,7.28966}, +{12.131,16.661,4.39608,8.19289}, +{9.81023,10.731,6.67919,9.31523}, +{6.97712,10.166,8.4813,13.3432}, +{6.45378,7.44457,8.96504,11.9806}, +{8.70396,11.5729,7.15588,12.1524}, +{9.93058,14.0306,0.849502,1.80855}, +{8.32174,8.34616,7.52595,12.0431}, +{2.79979,5.93358,4.90296,7.6893}, +{0.72484,5.42439,3.48229,5.77743}, +{6.05275,10.2779,7.4252,7.72184}, +{4.41176,6.91184,11.8809,15.3923}, +{6.50435,8.04432,11.4826,15.3172}, +{12.16,14.3518,1.13763,4.17255}, +{7.82506,10.5124,8.05713,9.03876}}; +unsigned n9=66; +double test10[][4]={{15.9875,18.9768,15.3193,17.9811}, +{16.5669,19.7216,1.05824,1.58667}, +{8.80629,9.88527,9.71101,13.2142}, +{19.568,20.1767,3.28922,8.03561}, +{13.6363,15.6827,12.9329,16.6542}, +{2.32913,3.58085,8.28597,12.6503}, +{6.86597,11.2847,5.9172,10.236}, +{8.57413,11.0048,18.0203,18.4095}, +{7.68828,8.89193,9.52038,12.3945}, +{13.5784,15.499,0.824193,4.7533}, +{5.70392,8.26946,10.1955,12.8184}, +{17.9857,22.6483,14.2013,16.0377}, +{14.7965,16.4222,11.9332,16.5984}, +{20.5111,23.1383,0.355473,0.834461}, +{5.88763,9.2761,8.31995,11.6173}, +{13.8307,16.6334,17.2376,19.8715}, +{7.20005,8.99179,19.0137,23.483}, +{3.67112,6.97933,18.6142,21.1208}, +{0.936183,5.81945,5.11063,7.47703}, +{9.85383,12.4861,7.80027,11.677}, +{8.07584,11.1964,13.8571,17.9736}, +{8.07017,10.0661,8.42816,9.79417}, +{10.8259,11.6232,16.7028,19.3248}, +{18.55,19.3911,17.174,22.0082}, +{1.34073,1.93538,17.9341,20.4509}, +{11.7558,12.1994,0.295703,2.19289}, +{12.4063,13.662,0.965124,5.21391}, +{2.2033,2.85518,16.4455,20.0191}, +{6.3853,9.77239,0.892142,2.17773}, +{0.546736,5.29679,12.1949,15.2469}, +{14.1365,17.5213,14.7027,15.1512}, +{9.46879,11.9145,11.8539,14.4408}, +{8.49611,8.98075,17.1388,17.5066}, +{1.53577,2.52014,0.615943,4.13396}, +{7.12078,9.05901,20.3739,23.44}, +{2.7104,7.09713,16.4442,20.8587}, +{12.9707,14.2845,12.5642,16.2281}, +{13.5086,14.3207,17.7611,20.1056}, +{19.2264,24.1481,2.063,5.27645}, +{15.2016,18.2491,1.10228,3.37286}, +{16.7733,18.1385,2.35807,7.0123}, +{19.8272,21.9464,18.27,22.8376}, +{4.27133,8.48869,19.5925,21.488}, +{19.6951,23.7284,10.5207,11.1889}, +{0.799027,3.61863,1.42504,3.44902}, +{1.31871,5.95584,16.4147,18.2479}, +{19.8398,21.0495,15.2495,15.8842}, +{3.15773,5.76599,11.1562,12.2007}, +{4.61422,4.78559,16.6607,16.9497}, +{11.0064,11.5745,16.521,19.5463}, +{13.3865,15.7969,12.215,14.3112}, +{0.272424,4.59201,7.19502,9.58004}, +{15.6377,16.4926,18.5978,19.0178}, +{1.44957,1.65985,5.24023,10.1284}, +{0.0559948,0.138395,3.75354,4.46554}, +{3.24015,3.86196,12.205,14.0543}, +{2.64686,3.51587,16.1429,16.6103}, +{2.56003,5.14236,5.6624,8.31491}, +{13.7143,16.5806,7.32777,10.6354}, +{15.8994,20.4036,0.171759,0.567584}, +{11.1247,11.5263,7.61341,8.80042}, +{10.7869,11.8353,7.73861,8.39933}, +{16.7563,18.1604,15.6377,20.3633}, +{4.7627,5.87556,0.850618,4.25755}, +{11.2178,15.6734,14.2378,15.9026}, +{2.00323,5.94744,1.78428,4.77571}, +{16.0705,20.0359,9.50528,12.9563}, +{14.9808,18.3586,9.56819,10.8817}, +{13.7005,17.173,10.5755,15.5172}, +{6.24185,6.44174,11.9766,16.0609}, +{14.0767,16.1476,11.9904,14.2274}, +{18.3009,20.9378,0.109473,0.330122}, +{0.395109,4.35458,19.8694,23.5078}, +{17.4949,22.4626,6.16132,10.5268}, +{0.992178,2.11099,18.813,22.5419}, +{8.41369,12.6754,20.0682,22.6}, +{19.5239,23.6359,3.22945,3.81068}, +{6.60361,6.84761,11.8174,12.6899}, +{8.95351,9.96275,11.2373,12.3269}, +{13.8414,17.1229,18.182,20.7568}, +{13.0468,17.4872,16.8349,21.2615}, +{16.6053,17.1026,5.24778,8.1272}, +{1.20043,2.96974,10.1904,13.8153}, +{7.73924,7.74809,1.53703,3.76274}, +{15.0915,18.4866,18.6576,18.9426}, +{10.69,13.9811,6.92511,9.44625}, +{8.66032,12.8382,6.67974,9.08735}, +{3.24707,3.91176,7.21641,8.75134}, +{20.5281,23.518,5.04016,5.38868}, +{8.78238,13.6922,11.9149,12.334}, +{19.1358,19.5264,15.9157,16.8192}, +{4.52551,7.52884,12.1049,16.4566}, +{18.467,22.8957,2.97024,7.48362}, +{17.9618,18.9449,2.7601,4.06645}, +{10.8057,15.3718,7.7254,8.32173}, +{19.6416,21.5781,7.62473,11.5731}, +{5.14712,8.87694,0.495145,1.50088}, +{4.11719,6.22953,3.59814,8.25023}, +{6.34314,9.83141,1.90886,3.52039}, +{11.6041,11.7642,12.6177,16.2647}, +{17.4351,19.786,0.846214,2.85357}, +{7.90974,12.4031,10.5818,10.868}, +{3.33578,5.53021,19.271,22.6137}, +{14.3296,18.1074,3.76864,6.21134}, +{1.39798,4.21194,14.7015,18.9814}, +{13.3463,13.89,4.76333,8.78979}, +{7.78517,12.3834,12.0445,12.1204}, +{1.21553,4.14149,10.9523,11.5827}, +{10.7328,15.0635,11.2248,16.0148}, +{1.89816,6.42421,6.21479,9.51491}, +{5.76369,9.87896,0.471237,2.08597}, +{1.10543,3.50571,6.4243,6.85217}, +{13.4916,16.9187,13.4167,14.751}, +{6.61683,9.79075,4.44435,7.2165}, +{17.5276,21.8159,3.22316,7.12862}, +{8.09408,10.3727,0.167984,1.77021}, +{8.04815,12.6168,7.91666,11.0816}, +{1.32248,2.63905,12.5164,17.4845}, +{7.324,11.7358,9.05354,13.7152}, +{15.0274,18.5751,11.55,13.6444}, +{15.3627,16.1478,19.7391,21.3528}, +{16.5701,19.0741,18.0876,18.9877}, +{19.9719,20.1289,10.2999,14.2899}, +{5.77124,9.49847,20.3551,23.9988}, +{9.4065,13.7029,1.45775,2.17524}, +{8.22117,12.8533,16.9079,17.5996}, +{8.20293,12.4012,15.7691,15.783}, +{9.33037,11.8253,0.286895,2.70091}, +{12.5114,14.6471,11.0241,13.8678}, +{14.6423,15.2091,5.08987,9.29257}, +{10.4729,12.308,1.7717,6.27227}, +{9.65187,11.9638,14.3196,18.937}, +{5.1704,6.94718,18.4884,22.8028}, +{4.66015,8.43071,12.6095,14.2635}, +{19.5384,21.1589,7.47562,10.9592}, +{20.3595,24.407,0.804689,2.94465}, +{0.775119,2.53222,1.35017,2.38185}, +{14.1459,18.0717,13.111,17.3643}, +{15.9535,16.9371,3.47482,6.36462}, +{15.1727,17.7769,13.1324,16.2993}, +{17.2678,19.5719,19.2912,23.3942}, +{14.5832,17.1443,19.2559,24.0751}, +{1.57289,3.42857,7.75497,11.9183}, +{2.63994,5.18274,5.84108,8.64802}, +{7.56056,8.51991,0.284378,0.750091}, +{8.4225,12.0985,13.1443,16.5509}, +{12.4397,13.7349,16.1177,21.0089}, +{18.411,22.1179,12.4302,16.1478}, +{16.7343,19.9381,0.87138,4.38391}, +{0.729191,5.0941,0.4316,3.36382}, +{7.96699,10.079,15.0613,19.489}, +{14.4215,16.2705,13.932,15.6623}, +{9.37756,12.4608,12.8857,16.6014}, +{12.0729,12.5163,2.59841,7.39714}, +{7.52658,11.0203,15.2853,19.805}, +{16.0919,20.3462,13.6464,15.1218}, +{6.17075,10.0034,17.5729,21.8258}, +{8.94533,11.0185,7.98461,12.5047}, +{0.249775,1.8787,2.72361,7.6554}, +{11.5167,11.8826,8.7937,10.8008}, +{14.3038,17.8052,19.0873,20.7193}, +{19.7272,24.1131,5.29434,7.64106}, +{19.7624,20.0966,13.2827,17.354}, +{5.58186,7.99298,3.3987,5.8269}, +{19.7479,20.3262,16.1492,17.465}, +{3.25902,6.3684,17.0948,20.9851}, +{12.7549,14.4322,1.40931,6.02218}, +{12.232,13.2567,0.559319,3.07481}, +{0.138414,4.75571,14.9273,18.2745}, +{6.04241,6.23422,9.62104,10.3701}}; +unsigned n10=170; +double test11[][4]={{2.20847,5.99613,25.7684,29.5065}, +{4.38169,7.14163,-7.79499,-7.42678}, +{17.1816,19.4476,-5.03151,-3.38153}, +{10.6383,11.0169,-0.356332,3.85003}, +{13.3309,15.7634,21.4146,24.0122}, +{17.1354,20.5384,27.9053,29.8839}, +{4.82128,7.88931,4.90792,5.71239}, +{13.1802,14.7891,24.0123,26.5035}, +{9.1468,9.95493,-3.73661,-1.29955}, +{14.4021,17.8989,19.2669,23.5805}, +{3.53936,4.95206,17.2632,19.2913}, +{11.2732,15.3951,10.4298,11.6976}, +{9.82902,13.9892,17.9523,19.9811}, +{10.0265,11.0793,16.4791,17.5196}, +{1.27427,5.64116,7.85316,8.33764}, +{3.70992,7.16293,5.06311,6.98578}, +{9.95501,13.9876,-3.13412,-1.29965}, +{17.6086,21.8963,15.3022,17.9743}, +{2.05607,2.66477,-0.552748,0.286511}, +{12.6971,13.3533,-4.23798,-3.73671}, +{7.7961,11.69,7.35371,11.9837}, +{7.68167,9.93012,1.7933,3.98514}, +{1.2176,2.27018,0.286611,3.17168}, +{4.98578,7.91342,12.8464,16.1781}, +{16.5918,21.3527,4.59687,5.72758}, +{9.12809,9.56481,1.38197,2.061}, +{14.6904,19.1649,-3.38143,-1.21492}, +{11.3046,15.5357,14.6315,17.2819}, +{3.69836,4.52282,5.06311,5.67974}, +{12.2713,13.7058,11.6977,14.6314}, +{0.130993,3.26738,-4.32728,-3.7221}, +{11.4317,12.3544,19.9812,22.2083}, +{10.0298,10.1041,11.1483,12.7055}, +{16.2023,16.7313,1.49517,4.59677}, +{12.4149,15.8265,4.33334,6.45789}, +{17.575,19.9519,12.3124,15.3021}, +{17.0991,22.0233,3.78959,6.02599}, +{3.99216,5.32933,0.583351,0.882127}, +{16.5929,18.003,14.3823,17.6574}, +{13.5273,15.1372,16.4791,20.1285}, +{12.3687,15.2044,6.45799,7.83514}, +{8.04258,9.47375,17.3137,21.5515}, +{7.329,10.9322,7.65703,11.5161}, +{1.98895,2.89459,1.84656,3.17168}, +{0.520521,2.46608,6.71895,10.4866}, +{13.184,16.1474,6.45799,7.30869}, +{2.13915,4.58689,17.2632,19.8192}, +{15.8375,18.2786,15.9558,18.1255}, +{14.7223,16.4109,16.4791,17.3636}, +{4.00206,7.29287,-4.32728,-1.41062}, +{16.6028,18.6157,14.6315,17.1786}, +{3.19495,7.10528,-1.41052,0.583251}, +{1.69626,5.11997,0.326338,1.84646}, +{12.1579,12.759,-0.356332,0.328198}, +{3.51735,7.12098,5.71249,7.85306}, +{0.953512,5.10372,3.17178,5.06301}, +{13.2737,14.3319,18.7924,21.1975}, +{1.46188,5.99876,10.3471,12.8463}, +{8.39195,9.77825,1.66426,2.061}, +{1.81344,5.57851,-3.53802,0.326238}, +{1.31773,2.99152,29.5066,33.3419}, +{5.33625,7.15652,19.4265,19.8527}, +{0.432492,3.44635,7.60608,10.3589}, +{1.60933,2.36115,-1.16144,0.286511}, +{9.27774,10.4284,-1.86525,-1.56998}, +{11.8878,13.7671,-5.11518,-4.23808}, +{10.0073,10.2574,11.282,12.9297}, +{10.5778,11.703,0.629406,0.965262}, +{3.17349,7.96657,16.1782,17.2631}, +{11.2281,13.6998,12.2002,12.4339}, +{13.7166,18.3124,19.2669,21.4145}, +{10.5388,15.0813,0.328298,4.33324}, +{9.05987,12.0136,-1.29945,-0.356432}, +{6.74526,7.05518,-8.26859,-7.79509}, +{17.7736,20.6859,5.72768,8.29825}, +{2.22113,7.1491,21.4284,25.7683}, +{16.1247,17.7842,2.70437,3.3773}, +{8.34023,10.0276,13.9827,18.7779}, +{15.1872,18.2348,17.1787,17.2902}, +{16.5308,17.6299,6.45799,8.71682}, +{5.98601,9.22204,23.2905,26.0581}, +{7.64095,10.7424,18.778,22.0208}, +{15.0585,19.52,17.7993,19.2668}, +{17.646,20.037,0.451228,3.78949}, +{0.0160052,1.94859,4.68464,6.71885}, +{7.29434,9.17489,13.9827,17.3136}, +{17.7896,21.639,6.02609,9.48842}, +{4.43065,8.71164,19.8528,23.2904}, +{16.5231,21.0708,3.3774,4.59677}, +{14.2096,16.0172,17.282,17.9522}, +{8.32648,9.09478,3.98524,7.65693}, +{3.6703,7.6841,0.583351,4.90782}, +{9.90605,10.9591,11.5162,13.1508}, +{14.7669,18.5129,-1.21482,3.3773}, +{3.48104,6.74301,29.5066,30.5551}, +{9.22657,10.4539,-5.59946,-1.29955}, +{8.12181,8.34154,-2.11601,1.66416}, +{4.11375,5.37752,30.5552,34.3283}, +{9.11434,12.5991,8.88212,10.4297}, +{11.3365,14.9133,-8.77796,-4.9549}, +{15.7809,16.0235,-2.30357,0.667869}, +{15.4629,16.7224,4.59687,6.45789}, +{13.3766,16.7042,21.4146,25.1652}, +{7.87643,10.2361,12.8464,13.9826}, +{7.38842,11.7536,11.5162,16.479}, +{5.15799,9.74446,-7.42668,-4.32738}, +{16.0009,16.044,-3.82308,0.667869}, +{15.6318,18.7733,8.71692,11.607}, +{10.7258,12.2305,7.30879,8.88202}, +{8.17133,9.84923,-1.56988,1.38187}, +{3.5179,5.38762,0.583351,5.06301}, +{9.4516,10.8319,22.0209,26.7891}, +{9.94456,11.8221,19.9812,21.2926}, +{5.14479,8.31779,3.92878,7.65693}, +{14.6057,18.2633,0.667969,4.59677}, +{5.62784,8.67939,17.3137,19.4264}, +{10.9244,13.5481,-1.29955,-1.29945}, +{5.76759,6.30746,-3.722,-3.5131}, +{7.13259,9.6258,8.33774,11.5161}, +{1.05144,1.32443,10.359,10.9074}, +{16.4807,19.9127,26.5036,27.9052}, +{5.9629,7.66553,-1.41052,-1.14028}, +{13.6489,16.9728,22.2084,25.5279}, +{2.50777,4.43837,19.8193,21.4283}, +{1.57577,3.7409,15.383,18.2258}, +{17.1816,18.8466,17.2903,17.7992}, +{8.43156,13.0154,-4.9548,-3.13422}, +{1.88827,6.19077,6.98588,10.347}, +{14.73,15.2147,17.9523,18.7923}, +{5.55742,8.69305,2.0611,3.92868}}; +unsigned n11=130; +double test12[][4]={ +{4.92744,6.6604,4.27234,8.301}, +{1.54924,2.51053,4.48526,9.19033}, +{1.55587,5.56226,-0.660563,3.35611}, +{1.87055,2.251,3.56944,6.75421}, +{1.58179,2.94863,5.24022,8.78858}, +{1.88069,5.98638,3.94188,5.24012}, +{1.81447,5.62383,5.24022,9.22211}, +{4.06842,6.37182,-0.053975,3.94178}, +{4.03643,4.2387,3.35621,3.94178}, +{1.16362,3.67328,0.29063,3.01001}, +}; +unsigned n12=10; +int main() { + double c,t; + vector<Rectangle*> rs; + cout << "test1" << endl; + test(generateRects(test1,n1,rs),c,t); + cout << "test2" << endl; + test(generateRects(test2,n2,rs),c,t); + cout << "test3" << endl; + test(generateRects(test3,n3,rs),c,t); + cout << "test4" << endl; + test(generateRects(test4,n4,rs),c,t); + cout << "test5" << endl; + test(generateRects(test5,n5,rs),c,t); + cout << "test6" << endl; + test(generateRects(test6,n6,rs),c,t); + cout << "test7" << endl; + test(generateRects(test7,n7,rs),c,t); + cout << "test8" << endl; + test(generateRects(test8,n8,rs),c,t); + cout << "test9" << endl; + test(generateRects(test9,n9,rs),c,t); + cout << "test10" << endl; + test(generateRects(test10,n10,rs),c,t); + cout << "test11" << endl; + test(generateRects(test11,n11,rs),c,t); + cout << "test12" << endl; + test(generateRects(test12,n12,rs),c,t); + int max_size=100, repeats=100,step=10; + //srand(time(NULL)); + for(int i=10;i<=max_size;i+=step) { + //if(i%5==0) cout << i << endl; + double disp=0, time=0; + for(int repeat=repeats;repeat--;) { + vector<Rectangle*> rs; + generateRandomRects(i,rs); + //printRects(rs); + test(rs,c,t); + disp+=c; + time+=t; + } + disp/=repeats; + time/=repeats; + cout << i << "," << time << "," << disp << endl; + } + return 0; +} diff --git a/src/libvpsc/tests/satisfy_inc.cpp b/src/libvpsc/tests/satisfy_inc.cpp new file mode 100644 index 000000000..514b36e2f --- /dev/null +++ b/src/libvpsc/tests/satisfy_inc.cpp @@ -0,0 +1,666 @@ +/* + * 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. + * + * 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. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library in the file LICENSE; if not, + * write to the Free Software Foundation, Inc., 59 Temple Place, + * Suite 330, Boston, MA 02111-1307 USA + * +*/ + +#include <libvpsc/rectangle.h> +#include <libvpsc/variable.h> +#include <libvpsc/constraint.h> +#include <libvpsc/solve_VPSC.h> +#include <algorithm> +#include <cstdio> +#include <ctime> +#include <cmath> +#include <cassert> + +using namespace std; +using namespace vpsc; + +static inline double getRand(const int range) { + return (double)range*rand()/(RAND_MAX+1.0); +} +inline bool approxEquals(const double a, const double b) { + return fabs((double)a-b)<0.01; +} +typedef vector<Constraint*> CS; + +bool checkResult(unsigned n, Variable *a[], unsigned m, Constraint *c[], double expected[]=NULL) { + std::vector<Variable*> aa(a,a+n); + std::vector<Constraint*> cc(c,c+m); + IncSolver vpsc(aa,cc); + vpsc.solve(); +#ifdef MOSEK_AVAILABLE + //printf("Checking with mosek..."); + MosekEnv* menv = mosek_init_sep_ls(n,c,m); + float *b=new float[n]; + float *x=new float[n]; + for(unsigned i=0;i<n;i++) { + b[i]=a[i]->desiredPosition; + } + mosek_quad_solve_sep(menv,b,x); + mosek_delete(menv); +#endif + for(unsigned i=0;i<n;i++) { + char s=','; + if(i==n-1) s='\n'; +#ifdef MOSEK_AVAILABLE + //printf("%f(%f)%c",a[i]->finalPosition,x[i],s); + if(!(approxEquals(a[i]->finalPosition,x[i]))) { + return false; + } + assert(approxEquals(a[i]->finalPosition,x[i])); +#endif + if(expected) assert(approxEquals(a[i]->finalPosition,expected[i])); + } +#ifdef MOSEK_AVAILABLE + delete [] b; + delete [] x; +#endif + return true; +} +void dumpMatlabProblem(unsigned n, Variable *a[], unsigned m, Constraint *c[]){ + printf("H=2*eye(%d);\n",n); + printf("f=-2*[ "); + for(unsigned i=0;i<n;i++) { + printf("%f ",a[i]->desiredPosition); + } + printf("];\n"); + printf("s=[ "); + for(unsigned i=0;i<n;i++) { + printf("%f ",a[i]->scale); + } + printf("];\n"); + printf("C=zeros(%d,%d);\n",m,n); + for(unsigned i=0;i<m;i++) { + printf("C(%d,[%d %d])=[1 -1];\n",i+1,c[i]->left->id+1,c[i]->right->id+1); + } + printf("A=C*diag(s);\n"); + printf("b=[ "); + for(unsigned i=0;i<m;i++) { + printf("%f ",-1.*c[i]->gap); + } + printf("];\n"); + printf("quadprog(H,f,A,b)\n"); +} +void test1() { + cout << "Test 1..." << endl; + Variable *a[] = { + new Variable(0,2,1,1.), + new Variable(1,9,1,1), + new Variable(2,9,1,1), + new Variable(3,9,1,1), + new Variable(4,2,1,1)}; + Constraint *c[] = { + new Constraint(a[0],a[4],3), + new Constraint(a[0],a[1],3), + new Constraint(a[1],a[2],3), + new Constraint(a[2],a[4],3), + new Constraint(a[3],a[4],3)}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + double expected[]={1.4,4.4,7.4,7.4,10.4}; + checkResult(n,a,m,c,expected); + cout << "Test 1... done." << endl; +} +void test1a() { + cout << "Test 1a..." << endl; + /* matlab: + H=2*eye(2) + f=[0 0] + A=[ 2 -1 ] + b=[ -2 ] + quadprog(H,f,A,b) + */ + Variable *a[] = { + new Variable(0,0,1,2.), + new Variable(1,0,1,1)}; + Constraint *c[] = { + new Constraint(a[0],a[1],2)}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + double expected[]={-0.8,0.4}; + checkResult(n,a,m,c,expected); + cout << "Test 1a... done." << endl; +} +void test1b() { + cout << "Test 1b..." << endl; + /* matlab: + H=2*eye(2) + f=[0 0] + A=[ 1 -2 ] + b=[ -2 ] + quadprog(H,f,A,b) + */ + Variable *a[] = { + new Variable(0,0,1,1.), + new Variable(1,0,1,2)}; + Constraint *c[] = { + new Constraint(a[0],a[1],2)}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + double expected[]={-0.4,0.8}; + checkResult(n,a,m,c,expected); + cout << "Test 1b... done." << endl; +} +void test1c() { + cout << "Test 1c..." << endl; + /* matlab: + H=2*eye(3) + f=-2*[ 1 1 1 ] + s=[ 3 2 4 ] + C=zeros(2,3) + C(1,1:2)=[1 -1] + C(2,2:3)=[1 -1] + A=C*diag(s) + b=[-2 -2 ] + quadprog(H,f,A,b) + */ + Variable *a[] = { + new Variable(0,1,1,3), + new Variable(1,1,1,2), + new Variable(2,1,1,4)}; + Constraint *c[] = { + new Constraint(a[0],a[1],2), + new Constraint(a[1],a[2],2)}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + double expected[]={0.2623, 1.3934, 1.1967}; + checkResult(n,a,m,c,expected); + cout << "Test 1c... done." << endl; +} + +// no splits required +void test2() { + cout << "Test 2..." << endl; + Variable *a[] = { + new Variable(0,4,1), + new Variable(1,6,1), + new Variable(2,9,1), + new Variable(3,2,1), + new Variable(4,5,1)}; + Constraint *c[] = { + new Constraint(a[0],a[2],3), + new Constraint(a[0],a[3],3), + new Constraint(a[1],a[4],3), + new Constraint(a[2],a[4],3), + new Constraint(a[2],a[3],3), + new Constraint(a[3],a[4],3)}; + double expected[]={0.5,6,3.5,6.5,9.5}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + checkResult(n,a,m,c,expected); + cout << "Test 2... done." << endl; +} + +// split required +void test3() { + /* matlab: + H=2*eye(5) + f=-2*[ 5 6 7 4 3 ] + s=[ 1 1 1 1 1 ] + C=zeros(5,5) + C(1,[1 5])=[1 -1] + C(2,[2 3])=[1 -1] + C(3,[3 4])=[1 -1] + C(4,[3 5])=[1 -1] + C(5,[4 5])=[1 -1] + A=C*diag(s) + b=-3*ones(5,1) + quadprog(H,f,A,b) + */ + cout << "Test 3..." << endl; + Variable *a[] = { + new Variable(0,5,1), + new Variable(1,6,1), + new Variable(2,7,1), + new Variable(3,4,1), + new Variable(4,3,1)}; + Constraint *c[] = { + new Constraint(a[0],a[4],3), + new Constraint(a[1],a[2],3), + new Constraint(a[2],a[3],3), + new Constraint(a[2],a[4],3), + new Constraint(a[3],a[4],3)}; + double expected[]={5,0.5,3.5,6.5,9.5}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + checkResult(n,a,m,c,expected); + cout << "Test 3... done." << endl; +} +// split required +void test4() { + /* matlab: + H=2*eye(5) + f=-2*[ 7 1 6 0 2 ] + s=[ 5 8 3 1 7 ] + C=zeros(6,5) + C(1,[1 4])=[1 -1] + C(2,[1 2])=[1 -1] + C(3,[2 5])=[1 -1] + C(4,[3 5])=[1 -1] + C(5,[3 4])=[1 -1] + C(6,[4 5])=[1 -1] + A=C*diag(s) + b=-3*ones(6,1) + quadprog(H,f,A,b) + */ + cout << "Test 4..." << endl; + Variable *a[] = { + new Variable(0,7,1,1), + new Variable(1,1,1,1), + new Variable(2,6,1,1), + new Variable(3,0,1,1), + new Variable(4,2,1,1)}; + Constraint *c[] = { + new Constraint(a[0],a[3],3), + new Constraint(a[0],a[1],3), + new Constraint(a[1],a[4],3), + new Constraint(a[2],a[4],3), + new Constraint(a[2],a[3],3), + new Constraint(a[3],a[4],3)}; + double expected[]={0.8,3.8,0.8,3.8,6.8}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + checkResult(n,a,m,c,expected); + cout << "Test 4... done." << endl; +} +void test5() { + cout << "Test 5..." << endl; + Variable *a[] = { + new Variable(0,0,1), new Variable(1,9,1), new + Variable(2,1,1), new Variable(3,9,1), new + Variable(4,5,1), new Variable(5,1,1), new + Variable(6,2,1), new Variable(7,1,1), new + Variable(8,6,1), new Variable(9,3,1)}; + Constraint *c[] = { + new Constraint(a[0],a[3],3), new Constraint(a[1],a[8],3), + new Constraint(a[1],a[6],3), new Constraint(a[2],a[6],3), + new Constraint(a[3],a[5],3), new Constraint(a[3],a[6],3), + new Constraint(a[3],a[7],3), new Constraint(a[4],a[8],3), + new Constraint(a[4],a[7],3), new Constraint(a[5],a[8],3), + new Constraint(a[5],a[7],3), new Constraint(a[5],a[8],3), + new Constraint(a[6],a[9],3), new Constraint(a[7],a[8],3), + new Constraint(a[7],a[9],3), new Constraint(a[8],a[9],3) + }; + double expected[]={-3.71429,4,1,-0.714286,2.28571,2.28571,7,5.28571,8.28571,11.2857}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + checkResult(n,a,m,c,expected); + cout << "Test 5... done." << endl; +} +void test6() { + cout << "Test 6..." << endl; + Variable *a[] = { + new Variable(0,7,1), + new Variable(1,0,1), + new Variable(2,3,1), + new Variable(3,1,1), + new Variable(4,4,1) + }; + Constraint *c[] = { + new Constraint(a[0],a[3],3), + new Constraint(a[0],a[2],3), + new Constraint(a[1],a[4],3), + new Constraint(a[1],a[4],3), + new Constraint(a[2],a[3],3), + new Constraint(a[3],a[4],3) + }; + double expected[]={-0.75,0,2.25,5.25,8.25}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + checkResult(n,a,m,c,expected); + cout << "Test 6... done." << endl; +} +void test7() { + cout << "Test 7..." << endl; + Variable *a[] = { + new Variable(0,4,1), + new Variable(1,2,1), + new Variable(2,3,1), + new Variable(3,1,1), + new Variable(4,8,1) + }; + Constraint *c[] = { + new Constraint(a[0],a[4],3), + new Constraint(a[0],a[2],3), + new Constraint(a[1],a[3],3), + new Constraint(a[2],a[3],3), + new Constraint(a[2],a[4],3), + new Constraint(a[3],a[4],3) + }; + double expected[]={-0.5,2,2.5,5.5,8.5}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + checkResult(n,a,m,c,expected); + cout << "Test 7... done." << endl; +} +void test8() { + /* matlab: + H=2*eye(5) + f=-2*[ 3 4 0 5 6 ] + s=[ 1 1 1 1 1 ] + C=zeros(6,5) + C(1,[1 2])=[1 -1] + C(2,[1 3])=[1 -1] + C(3,[2 3])=[1 -1] + C(4,[2 5])=[1 -1] + C(5,[3 4])=[1 -1] + C(6,[4 5])=[1 -1] + A=C*diag(s) + b=-3*ones(6,1) + quadprog(H,f,A,b) + */ + // This cycles when using the heuristic of merging on the least + // violated, violated constraint first. + cout << "Test 8..." << endl; + Variable *a[] = { + new Variable(0,3,1), + new Variable(1,4,1), + new Variable(2,0,1), + new Variable(3,5,1), + new Variable(4,6,1) + }; + Constraint *c[] = { + new Constraint(a[0],a[1],3), + new Constraint(a[0],a[2],3), + new Constraint(a[1],a[2],3), + new Constraint(a[1],a[4],3), + new Constraint(a[2],a[3],3), + new Constraint(a[2],a[3],3), + new Constraint(a[3],a[4],3), + new Constraint(a[3],a[4],3) + }; + double expected[]={-2.4,0.6,3.6,6.6,9.6}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + checkResult(n,a,m,c,expected); + cout << "Test 8... done." << endl; +} +void test9() { + /* matlab: + H=2*eye(5) + f=-2*[ 8 2 6 5 3 ] + s=[ 1 1 1 1 1 ] + C=zeros(7,5) + C(1,[1 5])=[1 -1] + C(2,[1 4])=[1 -1] + C(3,[2 3])=[1 -1] + C(4,[2 5])=[1 -1] + C(5,[3 4])=[1 -1] + C(6,[3 5])=[1 -1] + C(7,[4 5])=[1 -1] + A=C*diag(s) + b=-3*ones(7,1) + quadprog(H,f,A,b) + */ + cout << "Test 9..." << endl; + Variable *a[] = { + new Variable(0,8,1), + new Variable(1,2,1), + new Variable(2,6,1), + new Variable(3,5,1), + new Variable(4,3,1)}; + Constraint *c[] = { + new Constraint(a[0],a[4],3), + new Constraint(a[0],a[3],3), + new Constraint(a[1],a[2],3), + new Constraint(a[1],a[4],3), + new Constraint(a[2],a[3],3), + new Constraint(a[2],a[4],3), + new Constraint(a[3],a[4],3)}; + double expected[]={3.6,0.6,3.6,6.6,9.6}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + checkResult(n,a,m,c,expected); + cout << "Test 9... done." << endl; +} + +void test10() { + cout << "Test 10..." << endl; + Variable *a[] = { + new Variable(0,8.56215,1,4.99888), +new Variable(1,1.27641,1,8.06009), +new Variable(2,6.28523,1,1.06585), +new Variable(3,4.09743,1,0.924166), +new Variable(4,0.369025,1,6.12702)}; + + Constraint *c[] = { + new Constraint(a[0],a[2],3), +new Constraint(a[0],a[1],3), +new Constraint(a[0],a[1],3), +new Constraint(a[1],a[3],3), +new Constraint(a[1],a[3],3), +new Constraint(a[1],a[2],3), +new Constraint(a[2],a[4],3), +new Constraint(a[2],a[4],3), +new Constraint(a[3],a[4],3), +new Constraint(a[3],a[4],3)}; + + //double expected[]={-1,2,5,5,8}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + std::vector<Variable*> aa(a,a+n); + std::vector<Constraint*> cc(c,c+m); + IncSolver vpsc(aa,cc); + vpsc.solve(); + assert(checkResult(n,a,m,c,NULL)); + cout << "Test 10... done." << endl; +} +void test11() { + cout << "Test 11..." << endl; + Variable *a[] = { + new Variable(0,1.31591,1,9.02545), +new Variable(1,1.48155,1,3.68918), +new Variable(2,3.5091,1,2.07033), +new Variable(3,3.47131,1,8.75145), +new Variable(4,0.77374,1,0.967941)}; + + Constraint *c[] = { +new Constraint(a[0],a[3],3), +new Constraint(a[0],a[1],3), +new Constraint(a[1],a[4],3), +new Constraint(a[1],a[2],3), +new Constraint(a[2],a[4],3), +new Constraint(a[2],a[4],3), +new Constraint(a[3],a[4],3), +new Constraint(a[3],a[4],3)}; + + //double expected[]={-1,2,5,5,8}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + //dumpMatlabProblem(n,a,m,c); + std::vector<Variable*> aa(a,a+n); + std::vector<Constraint*> cc(c,c+m); + IncSolver vpsc(aa,cc); + vpsc.solve(); + assert(checkResult(n,a,m,c,NULL)); + cout << "Test 11... done." << endl; +} +void test12() { + cout << "Test 12..." << endl; + Variable *a[] = { +new Variable(0,2.83063,1,6.67901), +new Variable(1,6.81696,1,7.28642), +new Variable(2,9.27616,1,0.918345), +new Variable(3,3.4094,1,3.39673), +new Variable(4,2.92492,1,2.36269)}; + + Constraint *c[] = { +new Constraint(a[0],a[3],3), +new Constraint(a[0],a[2],3), +new Constraint(a[0],a[1],3), +new Constraint(a[1],a[4],3), +new Constraint(a[1],a[4],3), +new Constraint(a[1],a[4],3), +new Constraint(a[2],a[4],3), +new Constraint(a[2],a[4],3), +new Constraint(a[3],a[4],3), +new Constraint(a[3],a[4],3), +new Constraint(a[3],a[4],3), +new Constraint(a[3],a[4],3)}; + + //double expected[]={-1,2,5,5,8}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + //dumpMatlabProblem(n,a,m,c); + assert(checkResult(n,a,m,c,NULL)); + cout << "Test 12... done." << endl; +} +void test13() { + cout << "Test 13..." << endl; + Variable *a[] = { +new Variable(0,0.485024,1,1), +new Variable(1,3.52714,1,1), +new Variable(2,4.01263,1,1), +new Variable(3,4.58524,1,1), +new Variable(4,5.40796,1,1)}; + + Constraint *c[] = { +new Constraint(a[0],a[4],3), +new Constraint(a[0],a[4],3), +new Constraint(a[0],a[4],3), +new Constraint(a[0],a[2],3), +new Constraint(a[1],a[3],3), +new Constraint(a[1],a[3],3), +new Constraint(a[1],a[2],3), +new Constraint(a[2],a[4],3), +new Constraint(a[2],a[4],3), +new Constraint(a[2],a[4],3), +new Constraint(a[2],a[3],3), +new Constraint(a[3],a[4],3), +new Constraint(a[3],a[4],3), +new Constraint(a[3],a[4],3)}; + + //double expected[]={-1,2,5,5,8}; + unsigned int n = sizeof(a)/sizeof(Variable*); + unsigned int m = sizeof(c)/sizeof(Constraint*); + //dumpMatlabProblem(n,a,m,c); + assert(checkResult(n,a,m,c,NULL)); + cout << "Test 13... done." << endl; +} + +// n=number vars +// m=max constraints per var +void rand_test(unsigned n, unsigned m) { + Variable **a=new Variable*[n]; + CS cs; + for(unsigned i=0;i<n;i++) { + a[i]=new Variable(i,getRand(10),1,1);//getRand(10)); + } + for(unsigned i=0;i<n-1;i++) { + for(int j=0;j<getRand(m)+1;j++) { + int e = static_cast<int>(i + getRand(n-1-i)+1); + cs.push_back(new Constraint(a[i],a[e],3)); + } + } + Constraint **acs=new Constraint*[cs.size()]; + for(unsigned i=0;i<cs.size();i++) { + acs[i]=cs[i]; + } + try { + if(!checkResult(n,a,cs.size(),acs)) { + throw "Check failed!"; + } + } catch (char const *msg) { + cout << msg << endl; + cout<<"digraph g {"<<endl; + for(CS::iterator i(cs.begin());i!=cs.end();i++) { + Constraint *c=*i; + cout << c->left->id << "->" << c->right->id << ";" << endl; + } + cout<<"}"<<endl; + for(unsigned i=0;i<n;i++) { + if(i!=0) cout << "," << endl; + cout << "new Variable("<<i<<","<<a[i]->desiredPosition<< ",1," + << a[i]->scale <<")"; + //cout << "a[i]->Pos="<<a[i]->position() << endl; + } + cout << "};" << endl; + for(CS::iterator i(cs.begin());i!=cs.end();i++) { + if(i!=cs.begin()) cout << "," << endl; + Constraint *c=*i; + //cout << c->left->id << "->" << c->right->id << ";" << endl; + cout << "new Constraint(a[" << c->left->id << "],a[" << c->right->id << "],3)"; + + } + cout << "};" << endl; + throw "test failed!"; + } + /* + for(unsigned i=0;i<n;i++) { + a[i]->desiredPosition=getRand(10); + } + vpsc.solve(); + try { + if(!checkResult(n,a,m,acs)) { + throw "2nd Check failed!"; + } + } catch (char const *msg) { + cout << msg << endl; + for(unsigned i=0;i<n;i++) { + if(i!=0) cout << "," << endl; + cout << "new Variable("<<i<<","<<a[i]->desiredPosition<< ",1)"; + //cout << "a[i]->Pos="<<a[i]->position() << endl; + } + cout << "};" << endl; + for(CS::iterator i(cs.begin());i!=cs.end();i++) { + if(i!=cs.begin()) cout << "," << endl; + Constraint *c=*i; + //cout << c->left->id << "->" << c->right->id << ";" << endl; + cout << "new Constraint(a[" << c->left->id << "],a[" << c->right->id << "],3)"; + + } + cout << "};" << endl; + throw "test failed!"; + } + */ + for_each(a,a+n,delete_object()); + delete [] a; + for_each(cs.begin(),cs.end(),delete_object()); + delete [] acs; +} +int main() { + srand(time(NULL)); + test10(); + test2(); + test3(); + test4(); + test5(); + test6(); + test7(); + test8(); + test9(); + test10(); + test11(); + test12(); + test13(); + for(int i=0;i<1000;i++) { + if(i%100==0) cout << "i=" << i << endl; + rand_test(100,3); + } + for(int i=0;i<10000;i++) { + if(i%100==0) cout << "i=" << i << endl; + rand_test(5,3); + } + return 0; +} diff --git a/src/libvpsc/variable.cpp b/src/libvpsc/variable.cpp index 29bf8dc5c..4466c6823 100644 --- a/src/libvpsc/variable.cpp +++ b/src/libvpsc/variable.cpp @@ -1,16 +1,31 @@ /* - * Authors: - * Tim Dwyer <tgdwyer@gmail.com> + * vim: ts=4 sw=4 et tw=0 wm=0 * - * Copyright (C) 2005 Authors + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. * - * Released under GNU LGPL. Read the file 'COPYING' for more information. - */ -#include "variable.h" + * 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 "libvpsc/variable.h" namespace vpsc { std::ostream& operator <<(std::ostream &os, const Variable &v) { - os << "(" << v.id << "=" << v.position() << ")"; - return os; + if(v.block) + os << "(" << v.id << "=" << v.position() << ")"; + else + os << "(" << v.id << "=" << v.desiredPosition << ")"; + return os; } } diff --git a/src/libvpsc/variable.h b/src/libvpsc/variable.h index 022754a7d..d6114eee6 100644 --- a/src/libvpsc/variable.h +++ b/src/libvpsc/variable.h @@ -1,52 +1,95 @@ /* - * Authors: - * Tim Dwyer <tgdwyer@gmail.com> + * vim: ts=4 sw=4 et tw=0 wm=0 * - * Copyright (C) 2005 Authors + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. * - * Released under GNU LGPL. Read the file 'COPYING' for more information. - */ -#ifndef SEEN_REMOVEOVERLAP_VARIABLE_H -#define SEEN_REMOVEOVERLAP_VARIABLE_H + * 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 +*/ + +#ifndef VPSC_VARIABLE_H +#define VPSC_VARIABLE_H #include <vector> #include <iostream> -#include "block.h" + +#include "libvpsc/block.h" +#include "libvpsc/assertions.h" namespace vpsc { class Constraint; typedef std::vector<Constraint*> Constraints; + +/** + * @brief A variable is comprised of an ideal position, final position and + * a weight. + * + * When creating a variable you specify an ideal value, and a weight---how + * much the variable wants to be at its ideal position. After solving the + * problem you can read back the final position for the variable. +*/ class Variable { friend std::ostream& operator <<(std::ostream &os, const Variable &v); + friend class Block; + friend class Constraint; + friend class Solver; public: - const int id; // useful in log files + int id; // useful in log files double desiredPosition; - const double weight; + double finalPosition; + double weight; // how much the variable wants to + // be at it's desired position + double scale; // translates variable to another space double offset; Block *block; bool visited; + bool fixedDesiredPosition; Constraints in; Constraints out; char *toString(); - inline Variable(const int id, const double desiredPos, const double weight) + inline Variable(const int id, const double desiredPos=-1.0, + const double weight=1.0, const double scale=1.0) : id(id) , desiredPosition(desiredPos) + , finalPosition(desiredPos) , weight(weight) + , scale(scale) , offset(0) , block(NULL) , visited(false) + , fixedDesiredPosition(false) { } - inline double position() const { - return block->posn+offset; + double dfdv(void) const { + return 2. * weight * ( position() - desiredPosition ); } - //double position() const; - virtual ~Variable(void){ - in.clear(); - out.clear(); +private: + inline double position(void) const { + return (block->ps.scale*block->posn+offset)/scale; + } + inline double unscaledPosition(void) const { + COLA_ASSERT(block->ps.scale == 1); + COLA_ASSERT(scale == 1); + return block->posn + offset; } }; + +//! @brief A vector of pointers to Variable objects. +typedef std::vector<Variable*> Variables; + } -#endif // SEEN_REMOVEOVERLAP_VARIABLE_H +#endif // VPSC_VARIABLE_H |
