moving trunk for module inkscape

(bzr r1)

26 files changed, 2615 insertions, 0 deletions

diff --git a/src/removeoverlap/.cvsignore b/src/removeoverlap/.cvsignore
new file mode 100644
index 000000000..e8014d011
--- /dev/null
+++ b/src/removeoverlap/.cvsignore
@@ -0,0 +1,5 @@
+Makefile
+Makefile.in
+.deps
+makefile
+.dirstamp
diff --git a/src/removeoverlap/Makefile_insert b/src/removeoverlap/Makefile_insert
new file mode 100644
index 000000000..e28304431
--- /dev/null
+++ b/src/removeoverlap/Makefile_insert
@@ -0,0 +1,31 @@
+## Makefile.am fragment sourced by src/Makefile.am.
+
+removeoverlap/all: removeoverlap/libremoveoverlap.a
+
+removeoverlap/clean:
+	rm -f removeoverlap/libremoveoverlap.a $(removeoverlap_libremoveoverlap_a_OBJECTS)
+
+removeoverlap_libremoveoverlap_a_SOURCES =	\
+	removeoverlap/block.cpp	\
+	removeoverlap/block.h	\
+	removeoverlap/blocks.cpp	\
+	removeoverlap/blocks.h	\
+	removeoverlap/constraint.cpp	\
+	removeoverlap/constraint.h	\
+	removeoverlap/generate-constraints.cpp	\
+	removeoverlap/generate-constraints.h	\
+	removeoverlap/remove_rectangle_overlap.cpp	\
+	removeoverlap/remove_rectangle_overlap.h	\
+	removeoverlap/removeoverlap.cpp	\
+	removeoverlap/removeoverlap.h	\
+	removeoverlap/solve_VPSC.cpp	\
+	removeoverlap/solve_VPSC.h	\
+	removeoverlap/variable.cpp	\
+	removeoverlap/variable.h	\
+	removeoverlap/pairingheap/dsexceptions.h	\
+	removeoverlap/pairingheap/PairingHeap.cpp	\
+	removeoverlap/pairingheap/PairingHeap.h
+
+removeoverlap_remove_rectangle_overlap_test_SOURCES =	\
+	removeoverlap/remove_rectangle_overlap-test.cpp
+removeoverlap_remove_rectangle_overlap_test_LDADD = removeoverlap/libremoveoverlap.a -lglib-2.0
diff --git a/src/removeoverlap/block.cpp b/src/removeoverlap/block.cpp
new file mode 100644
index 000000000..799fa5d8e
--- /dev/null
+++ b/src/removeoverlap/block.cpp
@@ -0,0 +1,279 @@
+/**
+ * \brief Remove overlaps function
+ *
+ * Authors:
+ *   Tim Dwyer <tgdwyer@gmail.com>
+ *
+ * Copyright (C) 2005 Authors
+ *
+ * Released under GNU GPL.  Read the file 'COPYING' for more information.
+ */
+
+
+#include "constraint.h"
+#include "block.h"
+#include "blocks.h"
+#include "pairingheap/PairingHeap.h"
+#ifdef RECTANGLE_OVERLAP_LOGGING
+using std::ios;
+using std::ofstream;
+using std::endl;
+#endif
+using std::vector;
+
+void Block::addVariable(Variable *v) {
+	v->block=this;
+	vars->push_back(v);
+	weight+=v->weight;
+	wposn += v->weight * (v->desiredPosition - v->offset);
+	posn=wposn/weight;
+}
+Block::Block(Variable *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);
+	}
+}
+
+double Block::desiredWeightedPosition() {
+	double wp = 0;
+	for (vector<Variable*>::iterator v=vars->begin();v!=vars->end();v++) {
+		wp += ((*v)->desiredPosition - (*v)->offset) * (*v)->weight;
+	}
+	return wp;
+}
+Block::~Block(void)
+{
+	delete vars;
+	delete in;
+	delete out;
+}
+void Block::setUpInConstraints() {
+	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 (vector<Variable*>::iterator i=vars->begin();i!=vars->end();i++) {
+		Variable *v=*i;
+		vector<Constraint*> *cs=in?&(v->in):&(v->out);
+		for (vector<Constraint*>::iterator 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);
+			}
+		}
+	}
+}	
+/**
+ * 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) {
+	c->active=true;
+	wposn+=b->wposn-dist*b->weight;
+	weight+=b->weight;
+	posn=wposn/weight;
+	for(vector<Variable*>::iterator i=b->vars->begin();i!=b->vars->end();i++) {
+		Variable *v=*i;
+		v->block=this;
+		v->offset+=dist;
+		vars->push_back(v);
+	}
+}
+
+void Block::mergeIn(Block *b) {
+#ifdef RECTANGLE_OVERLAP_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);
+}
+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;
+#endif
+		if(lb == rb) {
+			// constraint has been merged into the same block
+			in->deleteMin();
+#ifdef RECTANGLE_OVERLAP_LOGGING
+			f<<" ... skipping internal constraint"<<endl;
+#endif
+		} else if(lb->timeStamp > rb->timeStamp 
+			&& v->timeStamp < lb->timeStamp 
+			|| v->timeStamp < rb->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 constraint"<<endl;
+#endif
+		} else {
+			break;
+		}
+	}
+	for(vector<Constraint*>::iterator 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;
+}
+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;
+}
+void Block::deleteMinInConstraint() {
+	in->deleteMin();
+}
+void Block::deleteMinOutConstraint() {
+	out->deleteMin();
+}
+inline bool Block::canFollowLeft(Constraint *c, Variable *last) {
+	return c->left->block==this && c->active && last!=c->left;
+}
+inline bool Block::canFollowRight(Constraint *c, Variable *last) {
+	return c->right->block==this && c->active && last!=c->right;
+}
+
+// computes the derivative of v and the lagrange multipliers
+// of v's out constraints (as the recursive sum of those below.
+// Does not backtrack over u.
+// also records the constraint with minimum lagrange multiplier
+// in min_lm
+double Block::compute_dfdv(Variable *v, Variable *u, Constraint *&min_lm) {
+	double dfdv=v->weight*(v->position() - v->desiredPosition);
+	for(vector<Constraint*>::iterator 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(min_lm==NULL||c->lm<min_lm->lm) min_lm=c;
+		}
+	}
+	for(vector<Constraint*>::iterator 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(min_lm==NULL||c->lm<min_lm->lm) min_lm=c;
+		}
+	}
+	return dfdv;
+}
+
+// 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 *v, Variable *u) {
+	for(vector<Constraint*>::iterator 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(vector<Constraint*>::iterator 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);
+		}
+	}
+}
+/**
+ * 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;
+}
+
+// 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 *v, Variable *u) {
+	b->addVariable(v);
+	for (vector<Constraint*>::iterator c=v->in.begin();c!=v->in.end();c++) {
+		if (canFollowLeft(*c,u))
+			populateSplitBlock(b, (*c)->left, v);
+	}
+	for (vector<Constraint*>::iterator c=v->out.begin();c!=v->out.end();c++) {
+		if (canFollowRight(*c,u)) 
+			populateSplitBlock(b, (*c)->right, v);
+	}
+}
+/**
+ * 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);
+}
+
+/**
+ * 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 (vector<Variable*>::iterator 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)
+{
+	os<<"Block:";
+	for(vector<Variable*>::iterator v=b.vars->begin();v!=b.vars->end();v++) {
+		os<<" "<<**v;
+	}
+    return os;
+}
diff --git a/src/removeoverlap/block.h b/src/removeoverlap/block.h
new file mode 100644
index 000000000..7905309bb
--- /dev/null
+++ b/src/removeoverlap/block.h
@@ -0,0 +1,59 @@
+/**
+ * \brief Remove overlaps function
+ *
+ * Authors:
+ *   Tim Dwyer <tgdwyer@gmail.com>
+ *
+ * Copyright (C) 2005 Authors
+ *
+ * Released under GNU GPL.  Read the file 'COPYING' for more information.
+ */
+
+#ifndef SEEN_REMOVEOVERLAP_BLOCK_H
+#define SEEN_REMOVEOVERLAP_BLOCK_H
+
+#include <vector>
+#include <iostream>
+class Variable;
+class Constraint;
+template <class T> class PairingHeap;
+class StupidPriorityQueue;
+
+class Block
+{
+	friend std::ostream& operator <<(std::ostream &os,const Block &b);
+public:
+	std::vector<Variable*> *vars;
+	double posn;
+	double weight;
+	double wposn;
+	Block(Variable *v=NULL);
+	~Block(void);
+	Constraint *findMinLM();
+	Constraint *findMinInConstraint();
+	Constraint *findMinOutConstraint();
+	void deleteMinInConstraint();
+	void deleteMinOutConstraint();
+	double desiredWeightedPosition();
+	void merge(Block *b, Constraint *c, double dist);
+	void mergeIn(Block *b);
+	void mergeOut(Block *b);
+	void split(Block *&l, Block *&r, Constraint *c);
+	void setUpInConstraints();
+	void setUpOutConstraints();
+	double cost();
+	bool deleted;
+	long timeStamp;
+	PairingHeap<Constraint*> *in;
+	PairingHeap<Constraint*> *out;
+private:
+	void reset_active_lm(Variable *v, Variable *u);
+	double compute_dfdv(Variable *v, Variable *u, Constraint *&min_lm);
+	bool canFollowLeft(Constraint *c, Variable *last);
+	bool canFollowRight(Constraint *c, Variable *last);
+	void populateSplitBlock(Block *b, Variable *v, Variable *u);
+	void addVariable(Variable *v);
+	void setUpConstraintHeap(PairingHeap<Constraint*>* &h,bool in);
+};
+
+#endif // SEEN_REMOVEOVERLAP_BLOCK_H
diff --git a/src/removeoverlap/blocks.cpp b/src/removeoverlap/blocks.cpp
new file mode 100644
index 000000000..45c479187
--- /dev/null
+++ b/src/removeoverlap/blocks.cpp
@@ -0,0 +1,190 @@
+/**
+ * \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
+ *
+ * Authors:
+ *   Tim Dwyer <tgdwyer@gmail.com>
+ *
+ * Copyright (C) 2005 Authors
+ *
+ * Released under GNU GPL.  Read the file 'COPYING' for more information.
+ */
+
+#include "blocks.h"
+#include "block.h"
+#include "constraint.h"
+#ifdef RECTANGLE_OVERLAP_LOGGING
+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;
+
+long blockTimeCtr;
+
+Blocks::Blocks(Variable *vs[], const int n) : vs(vs),nvs(n) {
+	blockTimeCtr=0;
+	for(int i=0;i<nvs;i++) {
+		insert(new Block(vs[i]));
+	}
+}
+Blocks::~Blocks(void)
+{
+	for(set<Block*>::iterator i=begin();i!=end();i++) {
+		delete *i;
+	}
+	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;
+}
+// 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);
+		}
+	}
+	order->push_front(v);
+}
+/**
+ * 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 RECTANGLE_OVERLAP_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;
+#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);
+		}
+		r->merge(l, c, dist);
+		r->mergeIn(l);
+		r->timeStamp=++blockTimeCtr;
+		removeBlock(l);
+		c=r->findMinInConstraint();
+	}		
+#ifdef RECTANGLE_OVERLAP_LOGGING
+	f<<"merged "<<*r<<endl;
+#endif
+}	
+/**
+ * Symmetrical to mergeLeft
+ */
+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;
+#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;
+#endif
+}
+void Blocks::removeBlock(Block *doomed) {
+	doomed->deleted=true;
+	//erase(doomed);
+}
+void Blocks::cleanup() {
+	vector<Block*> bcopy(size());
+	copy(begin(),end(),bcopy.begin());
+	for(vector<Block*>::iterator i=bcopy.begin();i!=bcopy.end();i++) {
+		Block *b=*i;
+		if(b->deleted) {
+			erase(b);
+			delete b;
+		}
+	}
+}
+/**
+ * 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;
+#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);
+
+	insert(l);
+	insert(r);
+}
+/**
+ * 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;
+}
+
diff --git a/src/removeoverlap/blocks.h b/src/removeoverlap/blocks.h
new file mode 100644
index 000000000..437af6310
--- /dev/null
+++ b/src/removeoverlap/blocks.h
@@ -0,0 +1,49 @@
+/**
+ * \brief Remove overlaps function
+ *
+ * Authors:
+ *   Tim Dwyer <tgdwyer@gmail.com>
+ *
+ * Copyright (C) 2005 Authors
+ *
+ * Released under GNU GPL.  Read the file 'COPYING' for more information.
+ */
+
+#ifndef SEEN_REMOVEOVERLAP_BLOCKS_H
+#define SEEN_REMOVEOVERLAP_BLOCKS_H
+
+#ifdef RECTANGLE_OVERLAP_LOGGING
+#define LOGFILE "cRectangleOverlap.log"
+#endif
+
+#include <set>
+#include <list>
+
+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
+ */
+class Blocks : public std::set<Block*>
+{
+public:
+	Blocks(Variable *vs[], const int n);
+	~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();
+private:
+	void dfsVisit(Variable *v, std::list<Variable*> *order);
+	void removeBlock(Block *doomed);
+	Variable **vs;
+	int nvs;
+};
+
+extern long blockTimeCtr;
+#endif // SEEN_REMOVEOVERLAP_BLOCKS_H
diff --git a/src/removeoverlap/constraint.cpp b/src/removeoverlap/constraint.cpp
new file mode 100644
index 000000000..78c5f03ad
--- /dev/null
+++ b/src/removeoverlap/constraint.cpp
@@ -0,0 +1,29 @@
+/**
+ * \brief Remove overlaps function
+ *
+ * Authors:
+ *   Tim Dwyer <tgdwyer@gmail.com>
+ *
+ * Copyright (C) 2005 Authors
+ *
+ * Released under GNU GPL.  Read the file 'COPYING' for more information.
+ */
+
+#include "constraint.h"
+
+Constraint::Constraint(Variable *left, Variable *right, double gap)
+{
+	this->left=left; 
+	left->out.push_back(this);
+	this->right=right;
+	right->in.push_back(this);
+	this->gap=gap;
+	active=false;
+	visited=false;
+	timeStamp=0;
+}
+std::ostream& operator <<(std::ostream &os, const Constraint &c)
+{
+	os<<*c.left<<"+"<<c.gap<<"<="<<*c.right<<"("<<c.slack()<<")";
+	return os;
+}
diff --git a/src/removeoverlap/constraint.h b/src/removeoverlap/constraint.h
new file mode 100644
index 000000000..26afcefdd
--- /dev/null
+++ b/src/removeoverlap/constraint.h
@@ -0,0 +1,52 @@
+/**
+ * \brief Remove overlaps function
+ *
+ * Authors:
+ *   Tim Dwyer <tgdwyer@gmail.com>
+ *
+ * Copyright (C) 2005 Authors
+ *
+ * Released under GNU GPL.  Read the file 'COPYING' for more information.
+ */
+
+#ifndef SEEN_REMOVEOVERLAP_CONSTRAINT_H
+#define SEEN_REMOVEOVERLAP_CONSTRAINT_H
+
+#include <iostream>
+#include "variable.h"
+
+class Constraint
+{
+	friend std::ostream& operator <<(std::ostream &os,const Constraint &c);
+public:
+	Variable *left;
+	Variable *right;
+	double gap;
+	double lm;
+	Constraint(Variable *left, Variable *right, double gap);
+	~Constraint(void){};
+	inline double Constraint::slack() const { return right->position() - gap - left->position(); }
+	//inline bool operator<(Constraint const &o) const { return slack() < o.slack(); }
+	long timeStamp;
+	bool active;
+	bool visited;
+};
+#include <float.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;
+	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;
+}
+
+#endif // SEEN_REMOVEOVERLAP_CONSTRAINT_H
diff --git a/src/removeoverlap/generate-constraints.cpp b/src/removeoverlap/generate-constraints.cpp
new file mode 100644
index 000000000..3238a0ca9
--- /dev/null
+++ b/src/removeoverlap/generate-constraints.cpp
@@ -0,0 +1,302 @@
+/**
+ * \brief Remove overlaps function
+ *
+ * Authors:
+ *   Tim Dwyer <tgdwyer@gmail.com>
+ *
+ * Copyright (C) 2005 Authors
+ *
+ * Released under GNU GPL.  Read the file 'COPYING' for more information.
+ */
+
+#include <set>
+#include <cassert>
+#include "generate-constraints.h"
+#include "constraint.h"
+
+#include "isnan.h" /* Include last */
+
+using std::set;
+using std::vector;
+
+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;
+	}
+	~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 (isNaN(u->pos) != isNaN(v->pos)) {
+		return isNaN(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.)
+	 */
+}
+
+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) {};
+};
+Event **events;
+int compare_events(const void *a, const void *b) {
+	Event *ea=*(Event**)a;
+	Event *eb=*(Event**)b;
+	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 );
+	} 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;
+}
+
+/**
+ * Prepares variables and constraints in order to apply VPSC horizontally.
+ * 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(Rectangle *rs[], double weights[], const int n, Variable **&vars, Constraint **&cs, bool useNeighbourLists) {
+	events=new Event*[2*n];
+	int i,m,ctr=0;
+	vector<Constraint*> constraints;
+	vars=new Variable*[n];
+	for(i=0;i<n;i++) {
+		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];
+		Node *v=e->v;
+		if(e->type==Open) {
+			scanline.insert(v);
+			if(useNeighbourLists) {
+				v->setNeighbours(
+					getLeftNeighbours(scanline,v),
+					getRightNeighbours(scanline,v)
+				);
+			} else {
+				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
+			int r;
+			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));
+					r=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));
+					r=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;
+				}
+			}
+			r=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 variables and constraints in order to apply VPSC vertically to remove ALL overlap.
+ */
+int generateYConstraints(Rectangle *rs[], double weights[], const int n, Variable **&vars, Constraint **&cs) {
+	events=new Event*[2*n];
+	int ctr=0,i,m;
+	vector<Constraint*> constraints;
+	vars=new Variable*[n];
+	for(i=0;i<n;i++) {
+		vars[i]=new Variable(i,rs[i]->getCentreY(),weights[i]);
+		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;
+	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/removeoverlap/generate-constraints.h b/src/removeoverlap/generate-constraints.h
new file mode 100644
index 000000000..ad9ccb1f9
--- /dev/null
+++ b/src/removeoverlap/generate-constraints.h
@@ -0,0 +1,78 @@
+/**
+ * \brief Remove overlaps function
+ *
+ * Authors:
+ *   Tim Dwyer <tgdwyer@gmail.com>
+ *
+ * Copyright (C) 2005 Authors
+ *
+ * Released under GNU GPL.  Read the file 'COPYING' for more information.
+ */
+
+#ifndef SEEN_REMOVEOVERLAP_GENERATE_CONSTRAINTS_H
+#define SEEN_REMOVEOVERLAP_GENERATE_CONSTRAINTS_H
+#include <iostream>
+
+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(Rectangle *rs[], double weights[], const int n, Variable **&vs, Constraint **&cs,bool useNeighbourLists);
+
+int generateYConstraints(Rectangle *rs[], double weights[], const int n, Variable **&vs, Constraint **&cs);
+
+#endif // SEEN_REMOVEOVERLAP_GENERATE_CONSTRAINTS_H
diff --git a/src/removeoverlap/makefile.in b/src/removeoverlap/makefile.in
new file mode 100644
index 000000000..480b25a90
--- /dev/null
+++ b/src/removeoverlap/makefile.in
@@ -0,0 +1,17 @@
+# Convenience stub makefile to call the real Makefile.
+
+@SET_MAKE@
+
+# Explicit so that it's the default rule.
+all:
+	cd .. && $(MAKE) removeoverlap/all
+
+clean %.a %.o:
+	cd .. && $(MAKE) removeoverlap/$@
+
+.PHONY: all clean
+
+OBJEXT = @OBJEXT@
+
+.SUFFIXES:
+.SUFFIXES: .a .$(OBJEXT)
diff --git a/src/removeoverlap/pairingheap/.cvsignore b/src/removeoverlap/pairingheap/.cvsignore
new file mode 100644
index 000000000..e8014d011
--- /dev/null
+++ b/src/removeoverlap/pairingheap/.cvsignore
@@ -0,0 +1,5 @@
+Makefile
+Makefile.in
+.deps
+makefile
+.dirstamp
diff --git a/src/removeoverlap/pairingheap/PairingHeap.cpp b/src/removeoverlap/pairingheap/PairingHeap.cpp
new file mode 100644
index 000000000..9c67f44fa
--- /dev/null
+++ b/src/removeoverlap/pairingheap/PairingHeap.cpp
@@ -0,0 +1,309 @@
+/**
+ * \brief 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 GPL 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 GPL.  Read the file 'COPYING' for more information.
+ */
+
+#include <vector>
+
+#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 &lhs, T &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( 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;
+	}
+}
+
+#endif
diff --git a/src/removeoverlap/pairingheap/PairingHeap.h b/src/removeoverlap/pairingheap/PairingHeap.h
new file mode 100644
index 000000000..586a591a8
--- /dev/null
+++ b/src/removeoverlap/pairingheap/PairingHeap.h
@@ -0,0 +1,111 @@
+/**
+ * \brief 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 GPL 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 GPL.  Read the file 'COPYING' for more information.
+ */
+#ifndef PAIRING_HEAP_H_
+#define PAIRING_HEAP_H_
+#include <stdlib.h>
+// 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>
+class PairNode
+{
+	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(const T &lhs, const T &rhs) const = 0;
+};
+
+template <class T>
+class PairingHeap
+{
+public:
+	PairingHeap( bool (*lessThan)(T &lhs, T &rhs) );
+	PairingHeap( const PairingHeap & rhs );
+	~PairingHeap( );
+
+	bool isEmpty( ) const;
+	bool isFull( ) const;
+	int size();
+
+	PairNode<T> *insert( const T & x );
+	const T & findMin( ) const;
+	void deleteMin( );
+	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 &lhs, T &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/removeoverlap/pairingheap/dsexceptions.h b/src/removeoverlap/pairingheap/dsexceptions.h
new file mode 100644
index 000000000..bef2c78c5
--- /dev/null
+++ b/src/removeoverlap/pairingheap/dsexceptions.h
@@ -0,0 +1,9 @@
+#ifndef DSEXCEPTIONS_H_
+#define DSEXCEPTIONS_H_
+
+class Underflow { };
+class Overflow  { };
+class OutOfMemory { };
+class BadIterator { };
+
+#endif
diff --git a/src/removeoverlap/placement_SolveVPSC.cpp b/src/removeoverlap/placement_SolveVPSC.cpp
new file mode 100755
index 000000000..a9f4344c8
--- /dev/null
+++ b/src/removeoverlap/placement_SolveVPSC.cpp
@@ -0,0 +1,130 @@
+#include <jni.h>
+#include "placement_SolveVPSC.h"
+#include <stdio.h>
+#include "solve_VPSC.h"
+#include "variable.h"
+#include "constraint.h"
+#include "remove_rectangle_overlap.h"
+#include "generate-constraints.h"
+#include <assert.h>
+#include <map>
+#define MaxSize 500
+
+JNIEXPORT jdouble JNICALL Java_placement_SolveVPSC_solve
+  (JNIEnv *env, jobject obj, jobjectArray vName, jdoubleArray vWeight, jdoubleArray vDesPos, jintArray cLeft, jintArray cRight, jdoubleArray cGap, jdoubleArray vResult, jint mode)
+{
+	jsize n = env->GetArrayLength(vWeight);
+	jsize m = env->GetArrayLength(cLeft);
+	int i;
+	double *lvWeight = env->GetDoubleArrayElements(vWeight, 0);
+	double *lvDesPos = env->GetDoubleArrayElements(vDesPos, 0);
+	long *lcLeft = env->GetIntArrayElements(cLeft, 0);
+	long *lcRight = env->GetIntArrayElements(cRight, 0);
+	double *lcGap = env->GetDoubleArrayElements(cGap, 0);
+	Variable **vs=new Variable*[n];
+	Constraint **cs=new Constraint*[m];
+	for (i=0; i<n; i++) {
+		jstring lvName = (jstring)env->GetObjectArrayElement(vName, i);
+		const char *name = env->GetStringUTFChars(lvName, NULL); 
+		// once upon a time variables had real names, now you'll have to 
+		// track them by number.
+		vs[i]=new Variable(i,lvDesPos[i],lvWeight[i]);
+	}
+	for (i=0; i<m; i++) {
+		cs[i]=new Constraint(vs[lcLeft[i]],vs[lcRight[i]],lcGap[i]);
+	}
+	double cost=0;
+	VPSC vpsc(vs,n,cs,m);
+	if(mode==0) {
+		vpsc.satisfy();
+	} else {
+		vpsc.solve();
+	}
+	for (i=0; i<n; i++) {
+		double p=vs[i]->position();
+		env->SetDoubleArrayRegion(vResult, i,1,&p);
+	}
+	for (i=0; i<m; i++) {
+		delete cs[i];
+	}
+	delete [] cs;
+	for (i=0; i<n; i++) {
+		delete vs[i];
+	}
+	env->ReleaseIntArrayElements(cLeft, lcLeft, 0);
+	env->ReleaseIntArrayElements(cRight, lcRight, 0);
+	env->ReleaseDoubleArrayElements(cGap, lcGap, 0);
+	env->ReleaseDoubleArrayElements(vWeight, lvWeight, 0);
+	env->ReleaseDoubleArrayElements(vDesPos, lvDesPos, 0);
+	delete [] vs;
+	return cost;
+}
+
+static Variable **vs;
+static Constraint **cs;
+static int m,n;
+JNIEXPORT jint JNICALL Java_placement_SolveVPSC_generateXConstraints
+(JNIEnv *env, jobject obj, jdoubleArray rMinX, jdoubleArray rMaxX, jdoubleArray rMinY, jdoubleArray rMaxY, jdoubleArray rWeight) {
+	n = (int)env->GetArrayLength(rWeight);
+	Rectangle **rs=new Rectangle*[n];
+	double *ws = env->GetDoubleArrayElements(rWeight, 0);
+	double *minX = env->GetDoubleArrayElements(rMinX, 0);
+	double *maxX = env->GetDoubleArrayElements(rMaxX, 0);
+	double *minY = env->GetDoubleArrayElements(rMinY, 0);
+	double *maxY = env->GetDoubleArrayElements(rMaxY, 0);
+	for(int i=0;i<n;i++) rs[i]=new Rectangle(minX[i],maxX[i],minY[i],maxY[i]);
+	m = generateXConstraints(rs, ws, n, vs, cs, true);
+	return m;
+}
+
+JNIEXPORT jint JNICALL Java_placement_SolveVPSC_generateYConstraints
+(JNIEnv *env, jobject obj, jdoubleArray rMinX, jdoubleArray rMaxX, jdoubleArray rMinY, jdoubleArray rMaxY, jdoubleArray rWeight) {
+	n = (int)env->GetArrayLength(rWeight);
+	Rectangle **rs=new Rectangle*[n];
+	double *ws = env->GetDoubleArrayElements(rWeight, 0);
+	double *minX = env->GetDoubleArrayElements(rMinX, 0);
+	double *maxX = env->GetDoubleArrayElements(rMaxX, 0);
+	double *minY = env->GetDoubleArrayElements(rMinY, 0);
+	double *maxY = env->GetDoubleArrayElements(rMaxY, 0);
+	for(int i=0;i<n;i++) rs[i]=new Rectangle(minX[i],maxX[i],minY[i],maxY[i]);
+	m = generateYConstraints(rs, ws, n, vs, cs);
+	return m;
+}
+using namespace std;
+JNIEXPORT void JNICALL Java_placement_SolveVPSC_getConstraints
+(JNIEnv *env, jobject obj, jintArray cLeft, jintArray cRight, jdoubleArray cGap) {
+	map<Variable*,int> vmap;
+	for(int i=0;i<n;i++) {
+		vmap[vs[i]]=i;
+	}
+	
+	for(int i=0;i<m;i++) {
+		jint l=vmap[cs[i]->left];
+		jint r=vmap[cs[i]->right];
+		double g=cs[i]->gap;
+		env->SetIntArrayRegion(cLeft, i,1,&l);
+		env->SetIntArrayRegion(cRight, i,1,&r);
+		env->SetDoubleArrayRegion(cGap, i,1,&g);
+	}
+}
+JNIEXPORT void JNICALL Java_placement_SolveVPSC_removeOverlaps
+(JNIEnv *env, jobject obj, jdoubleArray rMinX, jdoubleArray rMaxX, jdoubleArray rMinY, jdoubleArray rMaxY) {
+	//assert(1==2); //break for debugging
+	n = (int)env->GetArrayLength(rMinX);
+	Rectangle **rs=new Rectangle*[n];
+	double *minX = env->GetDoubleArrayElements(rMinX, 0);
+	double *maxX = env->GetDoubleArrayElements(rMaxX, 0);
+	double *minY = env->GetDoubleArrayElements(rMinY, 0);
+	double *maxY = env->GetDoubleArrayElements(rMaxY, 0);
+	for(int i=0;i<n;i++) rs[i]=new Rectangle(minX[i],maxX[i],minY[i],maxY[i]);
+	removeRectangleOverlap(rs,n,0,0);
+	for (i=0; i<n; i++) {
+		double x=rs[i]->getMinX();
+		double y=rs[i]->getMinY();
+		env->SetDoubleArrayRegion(rMinX, i,1,&x);
+		env->SetDoubleArrayRegion(rMinY, i,1,&y);
+	}
+	delete [] rs;
+	env->ReleaseDoubleArrayElements(rMaxX, maxX, 0);
+	env->ReleaseDoubleArrayElements(rMaxY, maxY, 0);
+}
\ No newline at end of file
diff --git a/src/removeoverlap/placement_SolveVPSC.h b/src/removeoverlap/placement_SolveVPSC.h
new file mode 100755
index 000000000..9f1c10cda
--- /dev/null
+++ b/src/removeoverlap/placement_SolveVPSC.h
@@ -0,0 +1,53 @@
+/* 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/removeoverlap/remove_rectangle_overlap-test.cpp b/src/removeoverlap/remove_rectangle_overlap-test.cpp
new file mode 100644
index 000000000..9999d027e
--- /dev/null
+++ b/src/removeoverlap/remove_rectangle_overlap-test.cpp
@@ -0,0 +1,308 @@
+#include "removeoverlap/remove_rectangle_overlap.h"
+#include <unistd.h>  // for alarm()
+#include <time.h>  // for srand seed and clock().
+#include <glib/gmacros.h>
+#include <glib/gmem.h>
+#include <cstdlib>
+#include <cmath>
+#include "removeoverlap/generate-constraints.h"
+#include "utest/utest.h"
+using std::abs;
+using std::rand;
+
+static bool
+possibly_eq(double const a, double const b)
+{
+    return abs(a - b) < 1e-13;
+}
+
+static bool
+possibly_le(double const a, double const b)
+{
+    return a - b < 1e-13;
+}
+
+static void
+show_rects(unsigned const n_rects, double const rect2coords[][4])
+{
+    for (unsigned i = 0; i < n_rects; ++i) {
+        printf("{%g, %g, %g, %g},\n",
+               rect2coords[i][0],
+               rect2coords[i][1],
+               rect2coords[i][2],
+               rect2coords[i][3]);
+    }
+}
+
+/**
+ * Returns the signum of x, but erring towards returning 0 if x is "not too far" from 0.  ("Not too
+ * far from 0" means [-0.9, 0.9] in current version.)
+ */
+static int
+sgn0(double const x)
+{
+    if (x <= -0.9) {
+        return -1;
+    } else if (0.9 <= x) {
+        return 1;
+    } else {
+        return 0;
+    }
+}
+
+static void
+test_case(unsigned const n_rects, double const rect2coords[][4])
+{
+    Rectangle **rs = (Rectangle **) g_malloc(sizeof(Rectangle*) * n_rects);
+    for (unsigned i = 0; i < n_rects; ++i) {
+        rs[i] = new Rectangle(rect2coords[i][0],
+                              rect2coords[i][1],
+                              rect2coords[i][2],
+                              rect2coords[i][3]);
+    }
+    removeRectangleOverlap(rs, n_rects, 0.0, 0.0);
+    for (unsigned i = 0; i < n_rects; ++i) {
+        UTEST_ASSERT(possibly_eq(rs[i]->width(), (rect2coords[i][1] -
+                                                  rect2coords[i][0]  )));
+        UTEST_ASSERT(possibly_eq(rs[i]->height(), (rect2coords[i][3] -
+                                                   rect2coords[i][2]  )));
+        for (unsigned j = 0; j < i; ++j) {
+            if (!( possibly_le(rs[i]->getMaxX(), rs[j]->getMinX()) ||
+                   possibly_le(rs[j]->getMaxX(), rs[i]->getMinX()) ||
+                   possibly_le(rs[i]->getMaxY(), rs[j]->getMinY()) ||
+                   possibly_le(rs[j]->getMaxY(), rs[i]->getMinY())   )) {
+                show_rects(n_rects, rect2coords);
+                char buf[32];
+                sprintf(buf, "[%u],[%u] of %u", j, i, n_rects);
+                utest__fail("Found overlap among ", buf, " rectangles");
+            }
+        }
+
+        /* Optimality test. */
+        {
+            bool found_block[2] = {false, false};
+            int const desired_movement[2] = {sgn0(rect2coords[i][0] - rs[i]->getMinX()),
+                                             sgn0(rect2coords[i][2] - rs[i]->getMinY())};
+            for (unsigned j = 0; j < n_rects; ++j) {
+                if (j == i)
+                    continue;
+                for (unsigned d = 0; d < 2; ++d) {
+                    if ( ( desired_movement[d] < 0
+                           ? abs(rs[j]->getMaxD(d) - rs[i]->getMinD(d))
+                           : abs(rs[i]->getMaxD(d) - rs[j]->getMinD(d)) )
+                         < .002 ) {
+                        found_block[d] = true;
+                    }
+                }
+            }
+
+            for (unsigned d = 0; d < 2; ++d) {
+                if ( !found_block[d]
+                     && desired_movement[d] != 0 ) {
+                    show_rects(n_rects, rect2coords);
+                    char buf[32];
+                    sprintf(buf, "%c in rectangle [%u] of %u", "XY"[d], i, n_rects);
+                    utest__fail("Found clear non-optimality in ", buf, " rectangles");
+                }
+            }
+        }
+    }
+    for (unsigned i = 0; i < n_rects; ++i) {
+        delete rs[i];
+    }
+    g_free(rs);
+}
+
+int main()
+{
+    srand(time(NULL));
+
+    /* Ensure that the program doesn't run for more than 30 seconds. */
+    alarm(30);
+
+    utest_start("removeRectangleOverlap(zero gaps)");
+
+    /* Derived from Bulia's initial test case.  This used to crash. */
+    UTEST_TEST("eg0") {
+        double case0[][4] = {
+            {-180.5, 69.072, 368.071, 629.071},
+            {99.5, 297.644, 319.5, 449.071},
+            {199.5, 483.358, 450.929, 571.929},
+            {168.071, 277.644, 462.357, 623.357},
+            {99.5, 99.751, 479.5, 674.786},
+            {-111.929, 103.358, 453.786, 611.929},
+            {-29.0714, 143.358, 273.786, 557.643},
+            {122.357, 269.072, 322.357, 531.929},
+            {256.643, 357.644, 396.643, 520.5}
+        };
+        test_case(G_N_ELEMENTS(case0), case0);
+    }
+
+#if 0 /* This involves a zero-height rect, so we'll ignore for the moment. */
+    UTEST_TEST("eg1") {
+        double case1[][4] = {
+            {5, 14, 9, 14},
+            {6, 13, 6, 8},
+            {11, 12, 5, 5},
+            {5, 8, 5, 7},
+            {12, 14, 14, 15},
+            {12, 14, 1, 14},
+            {1, 15, 14, 15},
+            {5, 6, 13, 13}
+        };
+        test_case(G_N_ELEMENTS(case1), case1);
+    }
+#endif
+
+    /* The next few examples used to result in overlaps. */
+    UTEST_TEST("eg2") {
+        double case2[][4] = {
+            {3, 4, 6, 13},
+            {0, 1, 0, 5},
+            {0, 4, 1, 6},
+            {2, 5, 0, 6},
+            {0, 10, 9, 13},
+            {5, 11, 1, 13},
+            {1, 2, 3, 8}
+        };
+        test_case(G_N_ELEMENTS(case2), case2);
+    }
+
+    UTEST_TEST("eg3") {
+        double case3[][4] = {
+            {0, 5, 0, 3},
+            {1, 2, 1, 3},
+            {3, 7, 4, 7},
+            {0, 9, 4, 5},
+            {3, 7, 0, 3}
+        };
+        test_case(G_N_ELEMENTS(case3), case3);
+    }
+
+    UTEST_TEST("eg4") {
+        double case4[][4] = {
+            {0, 1, 2, 3},
+            {0, 4, 0, 4},
+            {1, 6, 0, 4},
+            {2, 3, 4, 5},
+            {0, 5, 4, 6}
+        };
+        test_case(G_N_ELEMENTS(case4), case4);
+    }
+
+    UTEST_TEST("eg5") {
+        double case5[][4] = {
+            {1, 5, 1, 2},
+            {1, 6, 5, 7},
+            {6, 8, 1, 2},
+            {2, 3, 1, 4},
+            {5, 8, 2, 6}
+        };
+        test_case(G_N_ELEMENTS(case5), case5);
+    }
+
+    /* This one causes overlap in 2005-12-19 04:00 UTC version. */
+    UTEST_TEST("olap6") {
+        double case6[][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}
+        };
+        test_case(G_N_ELEMENTS(case6), case6);
+    }
+
+    /* The next two examples caused loops in the version at 2005-12-07 04:00 UTC. */
+    UTEST_TEST("loop0") {
+        double loop0[][4] = {
+            {13, 16, 6, 27},
+            {0, 6, 0, 12},
+            {11, 14, 1, 10},
+            {12, 39, 5, 24},
+            {14, 34, 4, 7},
+            {1, 30, 20, 27},
+            {1, 6, 1, 2},
+            {19, 28, 10, 24},
+            {4, 34, 15, 21},
+            {7, 13, 13, 34}
+        };
+        test_case(G_N_ELEMENTS(loop0), loop0);
+    }
+
+    UTEST_TEST("loop1") {
+        double loop1[][4] = {
+            {6, 18, 9, 16},
+            {8, 26, 10, 13},
+            {3, 10, 0, 14},
+            {0, 5, 16, 22},
+            {1, 8, 11, 21},
+            {1, 5, 0, 13},
+            {24, 25, 0, 2}
+        };
+        test_case(G_N_ELEMENTS(loop1), loop1);
+    }
+
+    UTEST_TEST("loop2") {
+        double loop2[][4] = {
+            {16, 22, 9, 16},
+            {8, 9, 14, 19},
+            {17, 25, 8, 13},
+            {10, 26, 26, 29},
+            {14, 19, 9, 19},
+            {0, 18, 3, 12},
+            {7, 8, 14, 22},
+            {14, 20, 25, 29}
+        };
+        test_case(G_N_ELEMENTS(loop2), loop2);
+    }
+
+    /* Random cases of up to 10 rectangles, with small non-neg int coords. */
+    for (unsigned n = 0; n <= 10; ++n) {
+        char buf[64];
+        sprintf(buf, "random ints with %u rectangles", n);
+        UTEST_TEST(buf) {
+            unsigned const fld_size = 8 * n;
+            double (*coords)[4] = (double (*)[4]) g_malloc(n * 4 * sizeof(double));
+            clock_t const clock_stop = clock() + CLOCKS_PER_SEC;
+            for (unsigned repeat = (n == 0 ? 1
+                                    : n == 1 ? 36
+                                    : (1 << 16)  ); repeat--;) {
+                for (unsigned i = 0; i < n; ++i) {
+                    for (unsigned d = 0; d < 2; ++d) {
+                        //unsigned const start = rand() % fld_size;
+                        //unsigned const end = start + rand() % (fld_size - start);
+                        unsigned const end = 1 + (rand() % (fld_size - 1));
+                        unsigned const start = rand() % end;
+                        coords[i][2 * d] = start;
+                        coords[i][2 * d + 1] = end;
+                    }
+                }
+                test_case(n, coords);
+                if (clock() >= clock_stop) {
+                    break;
+                }
+            }
+            g_free(coords);
+        }
+    }
+
+    return ( utest_end()
+             ? EXIT_SUCCESS
+             : EXIT_FAILURE );
+}
+
+
+/*
+  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:encoding=utf-8:textwidth=99 :
diff --git a/src/removeoverlap/remove_rectangle_overlap.cpp b/src/removeoverlap/remove_rectangle_overlap.cpp
new file mode 100755
index 000000000..30dbbaf9e
--- /dev/null
+++ b/src/removeoverlap/remove_rectangle_overlap.cpp
@@ -0,0 +1,109 @@
+#include <iostream>
+#include <cassert>
+#include "generate-constraints.h"
+#include "solve_VPSC.h"
+#include "variable.h"
+#include "constraint.h"
+#ifdef RECTANGLE_OVERLAP_LOGGING
+using std::ios;
+using std::ofstream;
+using std::endl;
+#endif
+
+#define EXTRA_GAP 0.0001
+
+double Rectangle::xBorder=0;
+double Rectangle::yBorder=0;
+/**
+ * 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(Rectangle *rs[], int n, double xBorder, double yBorder) {
+	assert(0 <= n);
+	try {
+	// The extra gap avoids numerical imprecision problems
+	Rectangle::setXBorder(xBorder+EXTRA_GAP);
+	Rectangle::setYBorder(yBorder+EXTRA_GAP);
+	double *ws=new double[n];
+	for(int i=0;i<n;i++) {
+		ws[i]=1;
+	}
+	Variable **vs;
+	Constraint **cs;
+	double *oldX = new double[n];
+	int m=generateXConstraints(rs,ws,n,vs,cs,true);
+	for(int i=0;i<n;i++) {
+		oldX[i]=vs[i]->desiredPosition;
+	}
+	VPSC vpsc_x(vs,n,cs,m);
+#ifdef RECTANGLE_OVERLAP_LOGGING
+	ofstream f(LOGFILE,ios::app);
+	f<<"Calling VPSC: Horizontal pass 1"<<endl;
+	f.close();
+#endif
+	vpsc_x.solve();
+	for(int i=0;i<n;i++) {
+		rs[i]->moveCentreX(vs[i]->position());
+		delete vs[i];
+	}
+	delete [] vs;
+	for(int 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(rs,ws,n,vs,cs);
+	VPSC vpsc_y(vs,n,cs,m);
+#ifdef RECTANGLE_OVERLAP_LOGGING
+	f.open(LOGFILE,ios::app);
+	f<<"Calling VPSC: Vertical pass"<<endl;
+	f.close();
+#endif
+	vpsc_y.solve();
+	for(int i=0;i<n;i++) {
+		rs[i]->moveCentreY(vs[i]->position());
+		rs[i]->moveCentreX(oldX[i]);
+		delete vs[i];
+	}
+	delete [] vs;
+	delete [] oldX;
+	for(int i = 0; i < m; ++i) {
+		delete cs[i];
+	}
+	delete [] cs;
+	Rectangle::setYBorder(Rectangle::yBorder-EXTRA_GAP);
+	m=generateXConstraints(rs,ws,n,vs,cs,false);
+	VPSC vpsc_x2(vs,n,cs,m);
+#ifdef RECTANGLE_OVERLAP_LOGGING
+	f.open(LOGFILE,ios::app);
+	f<<"Calling VPSC: Horizontal pass 2"<<endl;
+	f.close();
+#endif
+	vpsc_x2.solve();
+	for(int i=0;i<n;i++) {
+		rs[i]->moveCentreX(vs[i]->position());
+		delete vs[i];
+	}
+	delete [] vs;
+	for(int i = 0; i < m; ++i) {
+		delete cs[i];
+	}
+	delete [] cs;
+	delete [] ws;
+	} catch (char *str) {
+		std::cerr<<str<<std::endl;
+		for(int i=0;i<n;i++) {
+			std::cerr << *rs[i]<<std::endl;
+		}
+	}
+}
diff --git a/src/removeoverlap/remove_rectangle_overlap.h b/src/removeoverlap/remove_rectangle_overlap.h
new file mode 100755
index 000000000..9dc84f83a
--- /dev/null
+++ b/src/removeoverlap/remove_rectangle_overlap.h
@@ -0,0 +1,21 @@
+#ifndef REMOVE_RECTANGLE_OVERLAP_H_SEEN
+#define REMOVE_RECTANGLE_OVERLAP_H_SEEN
+
+/**
+ * \file Declaration of main internal remove-overlaps function.
+ */
+/*
+ * Authors:
+ *   Tim Dwyer <tgdwyer@gmail.com>
+ *
+ * Copyright (C) 2005 Authors
+ *
+ * Released under GNU GPL.  Read the file 'COPYING' for more information.
+ */
+
+class Rectangle;
+
+void removeRectangleOverlap(Rectangle *rs[], int n, double xBorder, double yBorder);
+
+
+#endif /* !REMOVE_RECTANGLE_OVERLAP_H_SEEN */
diff --git a/src/removeoverlap/removeoverlap.cpp b/src/removeoverlap/removeoverlap.cpp
new file mode 100644
index 000000000..9d7beb45f
--- /dev/null
+++ b/src/removeoverlap/removeoverlap.cpp
@@ -0,0 +1,80 @@
+/** \file
+ * Interface between Inkscape code (SPItem) and remove-overlaps function.
+ */
+/*
+* Authors:
+*   Tim Dwyer <tgdwyer@gmail.com>
+*
+* Copyright (C) 2005 Authors
+*
+* Released under GNU GPL.  Read the file 'COPYING' for more information.
+*/
+#include "util/glib-list-iterators.h"
+#include "sp-item.h"
+#include "sp-item-transform.h"
+#include "removeoverlap/generate-constraints.h"
+#include "removeoverlap/remove_rectangle_overlap.h"
+
+/**
+* Takes a list of inkscape items and moves them as little as possible
+* such that rectangular bounding boxes are separated by at least xGap
+* horizontally and yGap vertically
+*/
+void removeoverlap(GSList const *const items, double const xGap, double const yGap) {
+	if(!items) {
+		return;
+	}
+
+	using Inkscape::Util::GSListConstIterator;
+	std::list<SPItem *> selected;
+	selected.insert<GSListConstIterator<SPItem *> >(selected.end(), items, NULL);
+	if (selected.empty()) return;
+	int n=selected.size();
+
+	//Check 2 or more selected objects
+	if (n < 2) return;
+
+	Rectangle **rs = new Rectangle*[n];
+	int i=0;
+
+	NR::Point const gap(xGap, yGap);
+	for (std::list<SPItem *>::iterator it(selected.begin());
+		it != selected.end();
+		++it)
+	{
+		using NR::X; using NR::Y;
+		NR::Rect const item_box(sp_item_bbox_desktop(*it));
+		
+		/* The current algorithm requires widths & heights to be strictly positive. */
+		NR::Point min(item_box.min());
+		NR::Point max(item_box.max());
+		for (unsigned d = 0; d < 2; ++d) {
+			double const minsize = 1; // arbitrary positive number
+			if (max[d] - min[d] + gap[d] < minsize) {
+				double const mid = .5 * (min[d] + max[d]);
+				min[d] = mid - .5*minsize;
+				max[d] = mid + .5*minsize;
+			} else {
+				min[d] -= .5*gap[d];
+				max[d] += .5*gap[d];
+			}
+		}
+		rs[i++] = new Rectangle(min[X], max[X],
+					min[Y], max[Y]);
+	}
+	removeRectangleOverlap(rs, n, 0.0, 0.0);
+	i=0;
+	for (std::list<SPItem *>::iterator it(selected.begin());
+		it != selected.end();
+		++it)
+	{
+		NR::Rect const item_box(sp_item_bbox_desktop(*it));
+		Rectangle *r = rs[i++];
+		NR::Point const curr(item_box.midpoint());
+		NR::Point const dest(r->getCentreX(),
+				     r->getCentreY());
+		sp_item_move_rel(*it, NR::translate(dest - curr));
+		delete r;
+	}
+	delete [] rs;
+}
diff --git a/src/removeoverlap/removeoverlap.h b/src/removeoverlap/removeoverlap.h
new file mode 100644
index 000000000..b904f52f1
--- /dev/null
+++ b/src/removeoverlap/removeoverlap.h
@@ -0,0 +1,17 @@
+/**
+ * \brief Remove overlaps function
+ *
+ * Authors:
+ *   Tim Dwyer <tgdwyer@gmail.com>
+ *
+ * Copyright (C) 2005 Authors
+ *
+ * Released under GNU GPL.  Read the file 'COPYING' for more information.
+ */
+
+#ifndef SEEN_REMOVEOVERLAP_H
+#define SEEN_REMOVEOVERLAP_H
+
+void removeoverlap(GSList const *items, double xGap, double yGap);
+
+#endif // SEEN_REMOVEOVERLAP_H
diff --git a/src/removeoverlap/solve_VPSC.cpp b/src/removeoverlap/solve_VPSC.cpp
new file mode 100644
index 000000000..296cc415b
--- /dev/null
+++ b/src/removeoverlap/solve_VPSC.cpp
@@ -0,0 +1,265 @@
+/**
+ * \brief Remove overlaps function
+ *
+ * Authors:
+ *   Tim Dwyer <tgdwyer@gmail.com>
+ *
+ * Copyright (C) 2005 Authors
+ *
+ * Released under GNU GPL.  Read the file 'COPYING' for more information.
+ */
+
+#include <cassert>
+#include "constraint.h"
+#include "block.h"
+#include "blocks.h"
+#include "solve_VPSC.h"
+#ifdef RECTANGLE_OVERLAP_LOGGING
+using std::ios;
+using std::ofstream;
+using std::endl;
+#endif
+
+using std::list;
+using std::set;
+
+VPSC::VPSC(Variable *vs[], const int n, Constraint *cs[], const int m) : cs(cs), m(m) {
+	//assert(!constraintGraphIsCyclic(vs,n));
+	bs=new Blocks(vs,n);
+#ifdef RECTANGLE_OVERLAP_LOGGING
+	printBlocks();
+#endif
+}
+VPSC::~VPSC() {
+	delete bs;
+}
+
+// useful in debugging
+void VPSC::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(int i=0;i<m;i++) {
+		f<<"  "<<*cs[i]<<endl;
+	}
+#endif
+}
+/**
+* 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.
+*/
+void VPSC::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(int i=0;i<m;i++) {
+		if(cs[i]->slack()<-0.0000001) {
+#ifdef RECTANGLE_OVERLAP_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;
+}
+
+void VPSC::refine() {
+	bool solved=false;
+	// Solve shouldn't loop indefinately
+	// ... but just to make sure we limit the number of iterations
+	int 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;
+#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(int i=0;i<m;i++) {
+		if(cs[i]->slack()<-0.0000001) {
+			assert(cs[i]->slack()>-0.0000001);
+			throw "Unsatisfied constraint";
+		}
+	}
+}
+/**
+ * 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.
+ */
+void VPSC::solve() {
+	satisfy();
+	refine();
+}
+
+/**
+ * incremental version of solve that should allow refinement after blocks are
+ * moved.  Work in progress.
+ */
+void VPSC::move_and_split() {
+	//assert(!blockGraphIsCyclic());
+	for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();i++) {
+		Block *b=*i;
+		if(!b->deleted) {
+			b->wposn = b->desiredWeightedPosition();
+			b->posn = b->wposn / b->weight;
+			Variable *v=b->vars->front();
+			bs->mergeLeft(b);
+			// b may be merged away, so get any new block from one of its members
+			bs->mergeRight(v->block);
+		}
+	}
+	bs->cleanup();
+	// assert(!blockGraphIsCyclic());
+	refine();
+}
+
+#include <map>
+using std::map;
+using std::vector;
+struct node {
+	set<node*> in;
+	set<node*> out;
+};
+/*
+// useful in debugging - cycles would be BAD
+bool VPSC::constraintGraphIsCyclic(Variable *vs[], const int n) {
+	map<Variable*, node*> varmap;
+	vector<node*> graph;
+	for(int i=0;i<n;i++) {
+		node *u=new node;
+		graph.push_back(u);
+		varmap[vs[i]]=u;
+	}
+	for(int 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.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 VPSC::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();
+		}
+
+		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/removeoverlap/solve_VPSC.h b/src/removeoverlap/solve_VPSC.h
new file mode 100644
index 000000000..c7da502fb
--- /dev/null
+++ b/src/removeoverlap/solve_VPSC.h
@@ -0,0 +1,41 @@
+/**
+* \brief Remove overlaps function
+*
+* Authors:
+*   Tim Dwyer <tgdwyer@gmail.com>
+*
+* Copyright (C) 2005 Authors
+*
+* Released under GNU GPL.  Read the file 'COPYING' for more information.
+*/
+
+#ifndef SEEN_REMOVEOVERLAP_SOLVE_VPSC_H
+#define SEEN_REMOVEOVERLAP_SOLVE_VPSC_H
+
+class Variable;
+class Constraint;
+class Blocks;
+
+/**
+ * Variable Placement with Separation Constraints problem instance
+ */
+class VPSC {
+public:
+	void satisfy();
+	void solve();
+
+	void move_and_split();
+	VPSC(Variable *vs[], const int n, Constraint *cs[], const int m);
+	~VPSC();
+protected:
+	Blocks *bs;
+	void refine();
+private:
+	void printBlocks();
+	bool constraintGraphIsCyclic(Variable *vs[], const int n);
+	bool blockGraphIsCyclic();
+	Constraint **cs;
+	int m;
+};
+
+#endif // SEEN_REMOVEOVERLAP_SOLVE_VPSC_H
diff --git a/src/removeoverlap/variable.cpp b/src/removeoverlap/variable.cpp
new file mode 100644
index 000000000..0cf2e28a7
--- /dev/null
+++ b/src/removeoverlap/variable.cpp
@@ -0,0 +1,20 @@
+/**
+ * \brief Remove overlaps function
+ *
+ * Authors:
+ *   Tim Dwyer <tgdwyer@gmail.com>
+ *
+ * Copyright (C) 2005 Authors
+ *
+ * Released under GNU GPL.  Read the file 'COPYING' for more information.
+ */
+#include "variable.h"
+std::ostream& operator <<(std::ostream &os, const Variable &v) {
+	os << "(" << v.id << "=" << v.position() << ")";
+	return os;
+}
+
+#include "block.h"
+double Variable::position() const {
+	return block->posn+offset;
+}
diff --git a/src/removeoverlap/variable.h b/src/removeoverlap/variable.h
new file mode 100644
index 000000000..492e7504a
--- /dev/null
+++ b/src/removeoverlap/variable.h
@@ -0,0 +1,46 @@
+/**
+ * \brief Remove overlaps function
+ *
+ * Authors:
+ *   Tim Dwyer <tgdwyer@gmail.com>
+ *
+ * Copyright (C) 2005 Authors
+ *
+ * Released under GNU GPL.  Read the file 'COPYING' for more information.
+ */
+
+#ifndef SEEN_REMOVEOVERLAP_VARIABLE_H
+#define SEEN_REMOVEOVERLAP_VARIABLE_H
+
+#include <vector>
+#include <iostream>
+class Block;
+class Constraint;
+
+class Variable
+{
+	friend std::ostream& operator <<(std::ostream &os, const Variable &v);
+public:
+	static const unsigned int _TOSTRINGBUFFSIZE=20;
+	const int id; // useful in log files
+	double desiredPosition;
+	const double weight;
+	double offset;
+	Block *block;
+	bool visited;
+	std::vector<Constraint*> in;
+	std::vector<Constraint*> out;
+	char *toString();
+	inline Variable(const int id, const double desiredPos, const double weight)
+		: id(id)
+		, desiredPosition(desiredPos)
+		, weight(weight)
+	{
+	}
+	double position() const;
+	~Variable(void){
+		in.clear();
+		out.clear();
+	}
+};
+#endif // SEEN_REMOVEOVERLAP_VARIABLE_H