Fixed bug to do with comparison of invalid constraints in pairing heaps.

Also numerical problem with constraint generation fixed.

(bzr r30)

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 <cassert>
 #include "constraint.h"
 #include "block.h"
 #include "blocks.h"
 #include "pairingheap/PairingHeap.h"
 #ifdef RECTANGLE_OVERLAP_LOGGING
+#include <fstream>
 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<<endl;
+				f<<"     lb="<<*lb<<endl;
+				f<<"     rb="<<*rb<<endl;
+			}
+#endif
 			in->deleteMin();
 #ifdef RECTANGLE_OVERLAP_LOGGING
 			f<<" ... skipping internal constraint"<<endl;
diff --git a/src/removeoverlap/blocks.cpp b/src/removeoverlap/blocks.cpp
index 23df60516..13da8e15e 100644
--- a/src/removeoverlap/blocks.cpp
+++ b/src/removeoverlap/blocks.cpp
@@ -17,6 +17,7 @@
 #include "block.h"
 #include "constraint.h"
 #ifdef RECTANGLE_OVERLAP_LOGGING
+#include <fstream>
 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<Block*>::iterator i=begin();i!=end();i++) {
 		delete *i;
 	}
@@ -69,7 +71,11 @@ void Blocks::dfsVisit(Variable *v, list<Variable*> *order) {
 		if(!c->right->visited) {
 			dfsVisit(c->right, order);
 		}
-	}
+	}	
+#ifdef RECTANGLE_OVERLAP_LOGGING
+	ofstream f(LOGFILE,ios::app);
+	f<<"  order="<<*v<<endl;
+#endif
 	order->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 <cassert>
 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 <float.h>
+#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<Constraint*> constraints;
 	vars=new Variable*[n];
 	for(i=0;i<n;i++) {
+		assert(rs[i]->width()<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 T>
 class Comparator
 {
 public:
-	virtual bool isLessThan(const T &lhs, const T &rhs) const = 0;
+	virtual bool isLessThan(T &lhs, T &rhs) const = 0;
 };
 
 template <class T>
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 <fstream>
+#include <blocks.h>
 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 <fstream>
 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]<<endl;
 #endif
-			assert(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;