From b17e59ec53140e8fc55329abde9576d2c535fb32 Mon Sep 17 00:00:00 2001 From: tgdwyer Date: Thu, 26 Jan 2006 05:32:20 +0000 Subject: [PATCH] Fixed bug to do with comparison of invalid constraints in pairing heaps. Also numerical problem with constraint generation fixed. --- src/removeoverlap/block.cpp | 11 +++++-- src/removeoverlap/blocks.cpp | 8 ++++- src/removeoverlap/constraint.cpp | 5 ++- src/removeoverlap/constraint.h | 13 +++++--- src/removeoverlap/generate-constraints.cpp | 33 ++++++++++++------- src/removeoverlap/pairingheap/PairingHeap.h | 2 +- .../remove_rectangle_overlap.cpp | 2 ++ src/removeoverlap/solve_VPSC.cpp | 3 +- src/removeoverlap/variable.h | 2 ++ 9 files changed, 57 insertions(+), 22 deletions(-) diff --git a/src/removeoverlap/block.cpp b/src/removeoverlap/block.cpp index 32b310153..ebf56ea9e 100644 --- a/src/removeoverlap/block.cpp +++ b/src/removeoverlap/block.cpp @@ -8,13 +8,13 @@ * * Released under GNU GPL. Read the file 'COPYING' for more information. */ - - +#include #include "constraint.h" #include "block.h" #include "blocks.h" #include "pairingheap/PairingHeap.h" #ifdef RECTANGLE_OVERLAP_LOGGING +#include using std::ios; using std::ofstream; using std::endl; @@ -125,6 +125,13 @@ Constraint *Block::findMinInConstraint() { #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< using std::ios; using std::ofstream; using std::endl; @@ -37,6 +38,7 @@ Blocks::Blocks(Variable *vs[], const int n) : vs(vs),nvs(n) { } Blocks::~Blocks(void) { + blockTimeCtr=0; for(set::iterator i=begin();i!=end();i++) { delete *i; } @@ -69,7 +71,11 @@ void Blocks::dfsVisit(Variable *v, list *order) { if(!c->right->visited) { dfsVisit(c->right, order); } - } + } +#ifdef RECTANGLE_OVERLAP_LOGGING + ofstream f(LOGFILE,ios::app); + f<<" order="<<*v<push_front(v); } /** diff --git a/src/removeoverlap/constraint.cpp b/src/removeoverlap/constraint.cpp index 78c5f03ad..23da81927 100644 --- a/src/removeoverlap/constraint.cpp +++ b/src/removeoverlap/constraint.cpp @@ -10,9 +10,12 @@ */ #include "constraint.h" - +#include Constraint::Constraint(Variable *left, Variable *right, double gap) { + if(gap>1e40) { + int i=0; // this would most probably indicate a divide by zero somewhere + } this->left=left; left->out.push_back(this); this->right=right; diff --git a/src/removeoverlap/constraint.h b/src/removeoverlap/constraint.h index 26afcefdd..8760dcdf6 100644 --- a/src/removeoverlap/constraint.h +++ b/src/removeoverlap/constraint.h @@ -32,11 +32,16 @@ public: bool visited; }; #include +#include "block.h" static inline bool compareConstraints(Constraint *&l, Constraint *&r) { - double sl = l->slack(); - double sr = r->slack(); - if(l->left->block==l->right->block) sl=DBL_MIN; - if(r->left->block==r->right->block) sr=DBL_MIN; + double const sl = + l->left->block->timeStamp > l->timeStamp + ||l->left->block==l->right->block + ?DBL_MIN:l->slack(); + double const sr = + r->left->block->timeStamp > r->timeStamp + ||r->left->block==r->right->block + ?DBL_MIN:r->slack(); if(sl==sr) { // arbitrary choice based on id if(l->left->id==r->left->id) { diff --git a/src/removeoverlap/generate-constraints.cpp b/src/removeoverlap/generate-constraints.cpp index 3238a0ca9..98a60484a 100644 --- a/src/removeoverlap/generate-constraints.cpp +++ b/src/removeoverlap/generate-constraints.cpp @@ -43,6 +43,7 @@ struct Node { 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; @@ -139,7 +140,12 @@ Event **events; int compare_events(const void *a, const void *b) { Event *ea=*(Event**)a; Event *eb=*(Event**)b; - if(ea->pos > eb->pos) { + if(ea->v->r==ea->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; @@ -148,11 +154,6 @@ int compare_events(const void *a, const void *b) { return ( isNaN(ea->pos) ? -1 : 1 ); - } else if(ea->v->r==ea->v->r) { - // when comparing opening and closing from the same rect - // open must come first - if(ea->type==Open) return -1; - return 1; } return 0; } @@ -168,12 +169,14 @@ int generateXConstraints(Rectangle *rs[], double weights[], const int n, Variabl vector constraints; vars=new Variable*[n]; for(i=0;iwidth()<1e40); vars[i]=new Variable(i,rs[i]->getCentreX(),weights[i]); 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]; @@ -186,15 +189,19 @@ int generateXConstraints(Rectangle *rs[], double weights[], const int n, Variabl getRightNeighbours(scanline,v) ); } else { - NodeSet::iterator i=scanline.find(v); - if(i--!=scanline.begin()) { - Node *u=*i; + NodeSet::iterator it=scanline.find(v); + assert(*it==v); + if(it--!=scanline.begin()) { + assert(scanline.size()>1); + Node *u=*it; v->firstAbove=u; u->firstBelow=v; } - i=scanline.find(v); - if(++i!=scanline.end()) { - Node *u=*i; + it=scanline.find(v); + assert(*it==v); + if(++it!=scanline.end()) { + assert(scanline.size()>1); + Node *u=*it; v->firstBelow=u; u->firstAbove=v; } @@ -223,11 +230,13 @@ int generateXConstraints(Rectangle *rs[], double weights[], const int n, Variabl } else { Node *l=v->firstAbove, *r=v->firstBelow; if(l!=NULL) { + assert(l->firstBelow==v); 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) { + assert(r->firstAbove==v); double sep = (v->r->width()+r->r->width())/2.0; constraints.push_back(new Constraint(v->v,r->v,sep)); r->firstAbove=v->firstAbove; diff --git a/src/removeoverlap/pairingheap/PairingHeap.h b/src/removeoverlap/pairingheap/PairingHeap.h index 586a591a8..2f68c2b6f 100644 --- a/src/removeoverlap/pairingheap/PairingHeap.h +++ b/src/removeoverlap/pairingheap/PairingHeap.h @@ -57,7 +57,7 @@ template class Comparator { public: - virtual bool isLessThan(const T &lhs, const T &rhs) const = 0; + virtual bool isLessThan(T &lhs, T &rhs) const = 0; }; template diff --git a/src/removeoverlap/remove_rectangle_overlap.cpp b/src/removeoverlap/remove_rectangle_overlap.cpp index 30dbbaf9e..34cedf481 100755 --- a/src/removeoverlap/remove_rectangle_overlap.cpp +++ b/src/removeoverlap/remove_rectangle_overlap.cpp @@ -5,6 +5,8 @@ #include "variable.h" #include "constraint.h" #ifdef RECTANGLE_OVERLAP_LOGGING +#include +#include using std::ios; using std::ofstream; using std::endl; diff --git a/src/removeoverlap/solve_VPSC.cpp b/src/removeoverlap/solve_VPSC.cpp index 296cc415b..f2a7f0e85 100644 --- a/src/removeoverlap/solve_VPSC.cpp +++ b/src/removeoverlap/solve_VPSC.cpp @@ -15,6 +15,7 @@ #include "blocks.h" #include "solve_VPSC.h" #ifdef RECTANGLE_OVERLAP_LOGGING +#include using std::ios; using std::ofstream; using std::endl; @@ -72,7 +73,7 @@ void VPSC::satisfy() { ofstream f(LOGFILE,ios::app); f<<"Error: Unsatisfied constraint: "<<*cs[i]<slack()>-0.0000001); + //assert(cs[i]->slack()>-0.0000001); throw "Unsatisfied constraint"; } } diff --git a/src/removeoverlap/variable.h b/src/removeoverlap/variable.h index 492e7504a..e682dd7df 100644 --- a/src/removeoverlap/variable.h +++ b/src/removeoverlap/variable.h @@ -35,6 +35,8 @@ public: : id(id) , desiredPosition(desiredPos) , weight(weight) + , offset(0) + , visited(false) { } double position() const; -- 2.30.2