Updated libs from the Adaptagrams project: libavoid, libcola and libvspc; changed the code to match the new API

Signed-off-by: Sylvain Chiron <chironsylvain@orange.fr>

1 files changed, 548 insertions, 297 deletions

diff --git a/src/libvpsc/block.cpp b/src/libvpsc/block.cpp
index 8171780d4..a5e7ed0d1 100644
--- a/src/libvpsc/block.cpp
+++ b/src/libvpsc/block.cpp
@@ -1,208 +1,292 @@
 /*
- * Authors:
- *   Tim Dwyer <tgdwyer@gmail.com>
+ * vim: ts=4 sw=4 et tw=0 wm=0
  *
- * Copyright (C) 2005 Authors
+ * libvpsc - A solver for the problem of Variable Placement with 
+ *           Separation Constraints.
+ *
+ * Copyright (C) 2005-2008  Monash University
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ * See the file LICENSE.LGPL distributed with the library.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ *
+ * Author(s):  Tim Dwyer
+*/
+
+/*
+ * @brief A block is a group of variables that must be moved together to improve
+ * the goal function without violating already active constraints.
+ * The variables in a block are spanned by a tree of active constraints.
  *
- * Released under GNU LGPL.  Read the file 'COPYING' for more information.
  */
+
+#include "libvpsc/block.h"
+#include "libvpsc/variable.h"
 #include <cassert>
-#include "pairingheap/PairingHeap.h"
-#include "constraint.h"
-#include "block.h"
-#include "blocks.h"
-#ifdef RECTANGLE_OVERLAP_LOGGING
+#include "libvpsc/pairing_heap.h"
+#include "libvpsc/constraint.h"
+#include "libvpsc/exceptions.h"
+#include "libvpsc/blocks.h"
+
+#ifdef LIBVPSC_LOGGING
 #include <fstream>
 using std::ios;
 using std::ofstream;
 using std::endl;
 #endif
-using std::vector;
+
+#define __NOTNAN(p) (p)==(p)
 
 namespace vpsc {
-void Block::addVariable(Variable* const v) {
-	v->block=this;
-	vars->push_back(v);
-	weight+=v->weight;
-	wposn += v->weight * (v->desiredPosition - v->offset);
-	posn=wposn/weight;
-}
-Block::Block(Variable* const v) {
-	timeStamp=0;
-	posn=weight=wposn=0;
-	in=NULL;
-	out=NULL;
-	deleted=false;
-	vars=new vector<Variable*>;
-	if(v!=NULL) {
-		v->offset=0;
-		addVariable(v);
-	}
+void PositionStats::addVariable(Variable* v) {
+    double ai=scale/v->scale;
+    double bi=v->offset/v->scale;
+    double wi=v->weight;
+    AB+=wi*ai*bi;
+    AD+=wi*ai*v->desiredPosition;
+    A2+=wi*ai*ai;
+    /*
+#ifdef LIBVPSC_LOGGING
+    ofstream f(LOGFILE,ios::app);
+    f << "adding v[" << v->id << "], blockscale=" << scale << ", despos=" 
+      << v->desiredPosition << ", ai=" << ai << ", bi=" << bi
+      << ", AB=" << AB << ", AD=" << AD << ", A2=" << A2;
+#endif
+*/
+}
+void Block::addVariable(Variable* v) {
+    v->block=this;
+    vars->push_back(v);
+    if(ps.A2==0) ps.scale=v->scale;
+    //weight+= v->weight;
+    //wposn += v->weight * (v->desiredPosition - v->offset);
+    //posn=wposn/weight;
+    ps.addVariable(v);
+    posn=(ps.AD - ps.AB) / ps.A2;
+    COLA_ASSERT(__NOTNAN(posn));
+    /*
+#ifdef LIBVPSC_LOGGING
+    ofstream f(LOGFILE,ios::app);
+    f << ", posn=" << posn << endl;
+#endif
+*/
+}
+Block::Block(Blocks *blocks, Variable* const v)
+    : vars(new std::vector<Variable*>)
+    , posn(0)
+    //, weight(0)
+    //, wposn(0)
+    , deleted(false)
+    , timeStamp(0)
+    , in(NULL)
+    , out(NULL)
+    , blocks(blocks)
+{
+    if(v!=NULL) {
+        v->offset=0;
+        addVariable(v);
+    }
 }
 
-double Block::desiredWeightedPosition() {
-	double wp = 0;
-	for (Vit v=vars->begin();v!=vars->end();++v) {
-		wp += ((*v)->desiredPosition - (*v)->offset) * (*v)->weight;
-	}
-	return wp;
+void Block::updateWeightedPosition() {
+    //wposn=0;
+    ps.AB=ps.AD=ps.A2=0;
+    for (Vit v=vars->begin();v!=vars->end();++v) {
+        //wposn += ((*v)->desiredPosition - (*v)->offset) * (*v)->weight;
+        ps.addVariable(*v);
+    }
+    posn=(ps.AD - ps.AB) / ps.A2;
+    COLA_ASSERT(__NOTNAN(posn));
+#ifdef LIBVPSC_LOGGING
+    ofstream f(LOGFILE,ios::app);
+    f << ", posn=" << posn << endl;
+#endif
 }
 Block::~Block(void)
 {
-	delete vars;
-	delete in;
-	delete out;
+    delete vars;
+    delete in;
+    delete out;
 }
 void Block::setUpInConstraints() {
-	setUpConstraintHeap(in,true);
+    setUpConstraintHeap(in,true);
 }
 void Block::setUpOutConstraints() {
-	setUpConstraintHeap(out,false);
-}
-void Block::setUpConstraintHeap(PairingHeap<Constraint*>* &h,bool in) {
-	delete h;
-	h = new PairingHeap<Constraint*>(&compareConstraints);
-	for (Vit i=vars->begin();i!=vars->end();++i) {
-		Variable *v=*i;
-		vector<Constraint*> *cs=in?&(v->in):&(v->out);
-		for (Cit j=cs->begin();j!=cs->end();++j) {
-			Constraint *c=*j;
-			c->timeStamp=blockTimeCtr;
-			if ((c->left->block != this && in) || (c->right->block != this && !in)) {
-				h->insert(c);
-			}
-		}
-	}
-}	
-void Block::merge(Block* b, Constraint* c) {
-#ifdef RECTANGLE_OVERLAP_LOGGING
-	ofstream f(LOGFILE,ios::app);
-	f<<"  merging on: "<<*c<<",c->left->offset="<<c->left->offset<<",c->right->offset="<<c->right->offset<<endl;
+    setUpConstraintHeap(out,false);
+}
+void Block::setUpConstraintHeap(PairingHeap<Constraint*,CompareConstraints>* &h,bool in) {
+    delete h;
+    h = new PairingHeap<Constraint*,CompareConstraints>();
+    for (Vit i=vars->begin();i!=vars->end();++i) {
+        Variable *v=*i;
+        std::vector<Constraint*> *cs=in?&(v->in):&(v->out);
+        for (Cit j=cs->begin();j!=cs->end();++j) {
+            Constraint *c=*j;
+            c->timeStamp=blocks->blockTimeCtr;
+            if ( ((c->left->block != this) && in) || 
+                 ((c->right->block != this) && !in) )
+            {
+                h->insert(c);
+            }
+        }
+    }
+}    
+Block* Block::merge(Block* b, Constraint* c) {
+#ifdef LIBVPSC_LOGGING
+    ofstream f(LOGFILE,ios::app);
+    f<<"  merging on: "<<*c<<",c->left->offset="<<c->left->offset<<",c->right->offset="<<c->right->offset<<endl;
 #endif
-	double dist = c->right->offset - c->left->offset - c->gap;
-	Block *l=c->left->block;
-	Block *r=c->right->block;
-	if (vars->size() < b->vars->size()) {
-		r->merge(l,c,dist);
-	} else {
-	       	l->merge(r,c,-dist);
-	}
-#ifdef RECTANGLE_OVERLAP_LOGGING
-	f<<"  merged block="<<(b->deleted?*this:*b)<<endl;
+    double dist = c->right->offset - c->left->offset - c->gap;
+    Block *l=c->left->block;
+    Block *r=c->right->block;
+    if (l->vars->size() < r->vars->size()) {
+        r->merge(l,c,dist);
+    } else {
+               l->merge(r,c,-dist);
+    }
+    Block* mergeBlock=b->deleted?this:b;
+#ifdef LIBVPSC_LOGGING
+    f<<"  merged block="<<*mergeBlock<<endl;
 #endif
+    return mergeBlock;
 }
-
+/*
+ * Merges b into this block across c.  Can be either a
+ * right merge or a left merge
+ * @param b block to merge into this
+ * @param c constraint being merged
+ * @param distance separation required to satisfy c
+ */
 void Block::merge(Block *b, Constraint *c, double dist) {
-#ifdef RECTANGLE_OVERLAP_LOGGING
-	ofstream f(LOGFILE,ios::app);
-	f<<"    merging: "<<*b<<"dist="<<dist<<endl;
+#ifdef LIBVPSC_LOGGING
+    ofstream f(LOGFILE,ios::app);
+    f<<"    merging: "<<*b<<"dist="<<dist<<endl;
 #endif
-	c->active=true;
-	wposn+=b->wposn-dist*b->weight;
-	weight+=b->weight;
-	posn=wposn/weight;
-	for(Vit i=b->vars->begin();i!=b->vars->end();++i) {
-		Variable *v=*i;
-		v->block=this;
-		v->offset+=dist;
-		vars->push_back(v);
-	}
-	b->deleted=true;
+    c->active=true;
+    //wposn+=b->wposn-dist*b->weight;
+    //weight+=b->weight;
+    for(Vit i=b->vars->begin();i!=b->vars->end();++i) {
+        Variable *v=*i;
+        //v->block=this;
+        //vars->push_back(v);
+        v->offset+=dist;
+        addVariable(v);
+    }
+#ifdef LIBVPSC_LOGGING
+    for(Vit i=vars->begin();i!=vars->end();++i) {
+        Variable *v=*i;
+        f<<"    v["<<v->id<<"]: d="<<v->desiredPosition
+            <<" a="<<v->scale<<" o="<<v->offset
+            <<endl;
+    }
+    f<<"  AD="<<ps.AD<<" AB="<<ps.AB<<" A2="<<ps.A2<<endl;
+#endif
+    //posn=wposn/weight;
+    //COLA_ASSERT(wposn==ps.AD - ps.AB);
+    posn=(ps.AD - ps.AB) / ps.A2;
+    COLA_ASSERT(__NOTNAN(posn));
+    b->deleted=true;
 }
 
 void Block::mergeIn(Block *b) {
-#ifdef RECTANGLE_OVERLAP_LOGGING
-	ofstream f(LOGFILE,ios::app);
-	f<<"  merging constraint heaps... "<<endl;
+#ifdef LIBVPSC_LOGGING
+    ofstream f(LOGFILE,ios::app);
+    f<<"  merging constraint heaps... "<<endl;
 #endif
-	// We check the top of the heaps to remove possible internal constraints
-	findMinInConstraint();
-	b->findMinInConstraint();
-	in->merge(b->in);
-#ifdef RECTANGLE_OVERLAP_LOGGING
-	f<<"  merged heap: "<<*in<<endl;
+    // We check the top of the heaps to remove possible internal constraints
+    findMinInConstraint();
+    b->findMinInConstraint();
+    in->merge(b->in);
+#ifdef LIBVPSC_LOGGING
+    f<<"  merged heap: "<<*in<<endl;
 #endif
 }
-void Block::mergeOut(Block *b) {	
-	findMinOutConstraint();
-	b->findMinOutConstraint();
-	out->merge(b->out);
+void Block::mergeOut(Block *b) {    
+    findMinOutConstraint();
+    b->findMinOutConstraint();
+    out->merge(b->out);
 }
 Constraint *Block::findMinInConstraint() {
-	Constraint *v = NULL;
-	vector<Constraint*> outOfDate;
-	while (!in->isEmpty()) {
-		v = in->findMin();
-		Block *lb=v->left->block;
-		Block *rb=v->right->block;
-		// rb may not be this if called between merge and mergeIn
-#ifdef RECTANGLE_OVERLAP_LOGGING
-		ofstream f(LOGFILE,ios::app);
-		f<<"  checking constraint ... "<<*v;
-		f<<"    timestamps: left="<<lb->timeStamp<<" right="<<rb->timeStamp<<" constraint="<<v->timeStamp<<endl;
+    Constraint *v = NULL;
+    std::vector<Constraint*> outOfDate;
+    while (!in->isEmpty()) {
+        v = in->findMin();
+        Block *lb=v->left->block;
+        Block *rb=v->right->block;
+        // rb may not be this if called between merge and mergeIn
+#ifdef LIBVPSC_LOGGING
+        ofstream f(LOGFILE,ios::app);
+        f<<"  checking constraint ... "<<*v;
+        f<<"    timestamps: left="<<lb->timeStamp<<" right="<<rb->timeStamp<<" constraint="<<v->timeStamp<<endl;
 #endif
-		if(lb == rb) {
-			// constraint has been merged into the same block
-#ifdef RECTANGLE_OVERLAP_LOGGING
-			if(v->slack()<0) {
-				f<<"  violated internal constraint found! "<<*v<<endl;
-				f<<"     lb="<<*lb<<endl;
-				f<<"     rb="<<*rb<<endl;
-			}
+        if(lb == rb) {
+            // constraint has been merged into the same block
+#ifdef LIBVPSC_LOGGING
+            if(v->slack()<0) {
+                f<<"  violated internal constraint found! "<<*v<<endl;
+                f<<"     lb="<<*lb<<endl;
+                f<<"     rb="<<*rb<<endl;
+            }
 #endif
-			in->deleteMin();
-#ifdef RECTANGLE_OVERLAP_LOGGING
-			f<<" ... skipping internal constraint"<<endl;
+            in->deleteMin();
+#ifdef LIBVPSC_LOGGING
+            f<<" ... skipping internal constraint"<<endl;
 #endif
-		} else if(v->timeStamp < lb->timeStamp) {
-			// block at other end of constraint has been moved since this
-			in->deleteMin();
-			outOfDate.push_back(v);
-#ifdef RECTANGLE_OVERLAP_LOGGING
-			f<<"    reinserting out of date (reinsert later)"<<endl;
+        } else if(v->timeStamp < lb->timeStamp) {
+            // block at other end of constraint has been moved since this
+            in->deleteMin();
+            outOfDate.push_back(v);
+#ifdef LIBVPSC_LOGGING
+            f<<"    reinserting out of date (reinsert later)"<<endl;
 #endif
-		} else {
-			break;
-		}
-	}
-	for(Cit i=outOfDate.begin();i!=outOfDate.end();++i) {
-		v=*i;
-		v->timeStamp=blockTimeCtr;
-		in->insert(v);
-	}
-	if(in->isEmpty()) {
-		v=NULL;
-	} else {
-		v=in->findMin();
-	}
-	return v;
+        } else {
+            break;
+        }
+    }
+    for(Cit i=outOfDate.begin();i!=outOfDate.end();++i) {
+        v=*i;
+        v->timeStamp=blocks->blockTimeCtr;
+        in->insert(v);
+    }
+    if(in->isEmpty()) {
+        v=NULL;
+    } else {
+        v=in->findMin();
+    }
+    return v;
 }
 Constraint *Block::findMinOutConstraint() {
-	if(out->isEmpty()) return NULL;
-	Constraint *v = out->findMin();
-	while (v->left->block == v->right->block) {
-		out->deleteMin();
-		if(out->isEmpty()) return NULL;
-		v = out->findMin();
-	}
-	return v;
+    if(out->isEmpty()) return NULL;
+    Constraint *v = out->findMin();
+    while (v->left->block == v->right->block) {
+        out->deleteMin();
+        if(out->isEmpty()) return NULL;
+        v = out->findMin();
+    }
+    return v;
 }
 void Block::deleteMinInConstraint() {
-	in->deleteMin();
-#ifdef RECTANGLE_OVERLAP_LOGGING
-	ofstream f(LOGFILE,ios::app);
-	f<<"deleteMinInConstraint... "<<endl;
-	f<<"  result: "<<*in<<endl;
+    in->deleteMin();
+#ifdef LIBVPSC_LOGGING
+    ofstream f(LOGFILE,ios::app);
+    f<<"deleteMinInConstraint... "<<endl;
+    f<<"  result: "<<*in<<endl;
 #endif
 }
 void Block::deleteMinOutConstraint() {
-	out->deleteMin();
+    out->deleteMin();
 }
-inline bool Block::canFollowLeft(Constraint *c, const Variable* const last) {
-	return c->left->block==this && c->active && last!=c->left;
+inline bool Block::canFollowLeft(Constraint const* c, Variable const* last) const {
+    return c->left->block==this && c->active && last!=c->left;
 }
-inline bool Block::canFollowRight(Constraint *c, const Variable* const last) {
-	return c->right->block==this && c->active && last!=c->right;
+inline bool Block::canFollowRight(Constraint const* c, Variable const* last) const {
+    return c->right->block==this && c->active && last!=c->right;
 }
 
 // computes the derivative of v and the lagrange multipliers
@@ -211,32 +295,47 @@ inline bool Block::canFollowRight(Constraint *c, const Variable* const last) {
 // also records the constraint with minimum lagrange multiplier
 // in min_lm
 double Block::compute_dfdv(Variable* const v, Variable* const u,
-	       	Constraint *&min_lm) {
-	double dfdv=v->weight*(v->position() - v->desiredPosition);
-	for(Cit it=v->out.begin();it!=v->out.end();++it) {
-		Constraint *c=*it;
-		if(canFollowRight(c,u)) {
-			dfdv+=c->lm=compute_dfdv(c->right,v,min_lm);
-			if(!c->equality&&(min_lm==NULL||c->lm<min_lm->lm)) min_lm=c;
-		}
-	}
-	for(Cit it=v->in.begin();it!=v->in.end();++it) {
-		Constraint *c=*it;
-		if(canFollowLeft(c,u)) {
-			dfdv-=c->lm=-compute_dfdv(c->left,v,min_lm);
-			if(!c->equality&&(min_lm==NULL||c->lm<min_lm->lm)) min_lm=c;
-		}
-	}
-	return dfdv;
+               Constraint *&min_lm) {
+    double dfdv=v->dfdv();
+    for(Cit it=v->out.begin();it!=v->out.end();++it) {
+        Constraint *c=*it;
+        if(canFollowRight(c,u)) {
+            c->lm=compute_dfdv(c->right,v,min_lm);
+            dfdv+=c->lm*c->left->scale;
+            if(!c->equality&&(min_lm==NULL||c->lm<min_lm->lm)) min_lm=c;
+        }
+    }
+    for(Cit it=v->in.begin();it!=v->in.end();++it) {
+        Constraint *c=*it;
+        if(canFollowLeft(c,u)) {
+            c->lm=-compute_dfdv(c->left,v,min_lm);
+            dfdv-=c->lm*c->right->scale;
+            if(!c->equality&&(min_lm==NULL||c->lm<min_lm->lm)) min_lm=c;
+        }
+    }
+    return dfdv/v->scale;
+}
+double Block::compute_dfdv(Variable* const v, Variable* const u) {
+    double dfdv = v->dfdv();
+    for(Cit it = v->out.begin(); it != v->out.end(); ++it) {
+        Constraint *c = *it;
+        if(canFollowRight(c,u)) {
+            c->lm =   compute_dfdv(c->right,v);
+            dfdv += c->lm * c->left->scale;
+        }
+    }
+    for(Cit it=v->in.begin();it!=v->in.end();++it) {
+        Constraint *c = *it;
+        if(canFollowLeft(c,u)) {
+            c->lm = - compute_dfdv(c->left,v);
+            dfdv -= c->lm * c->right->scale;
+        }
+    }
+    return dfdv/v->scale;
 }
 
-
-// computes dfdv for each variable and uses the sum of dfdv on either side of
-// the constraint c to compute the lagrangian multiplier lm_c.
 // The top level v and r are variables between which we want to find the
 // constraint with the smallest lm.  
-// When we find r we pass NULL to subsequent recursive calls, 
-// thus r=NULL indicates constraints are not on the shortest path.
 // Similarly, m is initially NULL and is only assigned a value if the next
 // variable to be visited is r or if a possible min constraint is returned from
 // a nested call (rather than NULL).
@@ -244,153 +343,305 @@ double Block::compute_dfdv(Variable* const v, Variable* const u,
 // the recursion (checking only constraints traversed left-to-right 
 // in order to avoid creating any new violations).
 // We also do not consider equality constraints as potential split points
+bool Block::split_path(
+    Variable* r, 
+    Variable* const v, 
+    Variable* const u, 
+    Constraint* &m,
+    bool desperation=false
+    ) 
+{
+    for(Cit it(v->in.begin());it!=v->in.end();++it) {
+        Constraint *c=*it;
+        if(canFollowLeft(c,u)) {
+#ifdef LIBVPSC_LOGGING
+    ofstream f(LOGFILE,ios::app);
+    f<<"  left split path: "<<*c<<endl;
+#endif
+            if(c->left==r) {
+                if(desperation&&!c->equality) m=c;
+                return true;
+            } else {
+                if(split_path(r,c->left,v,m)) {
+                    if(desperation && !c->equality && (!m||c->lm<m->lm)) {
+                               m=c;
+                    }
+                    return true;
+                }
+            }
+        }
+    }
+    for(Cit it(v->out.begin());it!=v->out.end();++it) {
+        Constraint *c=*it;
+        if(canFollowRight(c,u)) {
+#ifdef LIBVPSC_LOGGING
+    ofstream f(LOGFILE,ios::app);
+    f<<"  right split path: "<<*c<<endl;
+#endif
+            if(c->right==r) {
+                if(!c->equality) m=c;
+                return true;
+            } else {
+                if(split_path(r,c->right,v,m)) {
+                    if(!c->equality && (!m||c->lm<m->lm))
+                               m=c;
+                    return true;
+                }
+            }
+        }
+    }
+    return false;
+}
+/*
 Block::Pair Block::compute_dfdv_between(
-		Variable* r, Variable* const v, Variable* const u, 
-		const Direction dir = NONE, bool changedDirection = false) {
-	double dfdv=v->weight*(v->position() - v->desiredPosition);
-	Constraint *m=NULL;
-	for(Cit it(v->in.begin());it!=v->in.end();++it) {
-		Constraint *c=*it;
-		if(canFollowLeft(c,u)) {
-			if(dir==RIGHT) { 
-				changedDirection = true; 
-			}
-			if(c->left==r) {
-			       	r=NULL;
-			        if(!c->equality) m=c; 
-			}
-			Pair p=compute_dfdv_between(r,c->left,v,
-					LEFT,changedDirection);
-			dfdv -= c->lm = -p.first;
-			if(r && p.second) 
-				m = p.second;
-		}
-	}
-	for(Cit it(v->out.begin());it!=v->out.end();++it) {
-		Constraint *c=*it;
-		if(canFollowRight(c,u)) {
-			if(dir==LEFT) { 
-				changedDirection = true; 
-			}
-			if(c->right==r) {
-			       	r=NULL; 
-			        if(!c->equality) m=c; 
-			}
-			Pair p=compute_dfdv_between(r,c->right,v,
-					RIGHT,changedDirection);
-			dfdv += c->lm = p.first;
-			if(r && p.second) 
-				m = changedDirection && !c->equality && c->lm < p.second->lm 
-					? c 
-					: p.second;
-		}
-	}
-	return Pair(dfdv,m);
+        Variable* r, Variable* const v, Variable* const u, 
+        const Direction dir = NONE, bool changedDirection = false) {
+    double dfdv=v->weight*(v->position() - v->desiredPosition);
+    Constraint *m=NULL;
+    for(Cit it(v->in.begin());it!=v->in.end();++it) {
+        Constraint *c=*it;
+        if(canFollowLeft(c,u)) {
+            if(dir==RIGHT) { 
+                changedDirection = true; 
+            }
+            if(c->left==r) {
+                       r=NULL;
+                    if(!c->equality) m=c; 
+            }
+            Pair p=compute_dfdv_between(r,c->left,v,
+                    LEFT,changedDirection);
+            dfdv -= c->lm = -p.first;
+            if(r && p.second) 
+                m = p.second;
+        }
+    }
+    for(Cit it(v->out.begin());it!=v->out.end();++it) {
+        Constraint *c=*it;
+        if(canFollowRight(c,u)) {
+            if(dir==LEFT) { 
+                changedDirection = true; 
+            }
+            if(c->right==r) {
+                       r=NULL; 
+                    if(!c->equality) m=c; 
+            }
+            Pair p=compute_dfdv_between(r,c->right,v,
+                    RIGHT,changedDirection);
+            dfdv += c->lm = p.first;
+            if(r && p.second) 
+                m = changedDirection && !c->equality && c->lm < p.second->lm 
+                    ? c 
+                    : p.second;
+        }
+    }
+    return Pair(dfdv,m);
 }
+*/
 
 // resets LMs for all active constraints to 0 by
 // traversing active constraint tree starting from v,
 // not back tracking over u
 void Block::reset_active_lm(Variable* const v, Variable* const u) {
-	for(Cit it=v->out.begin();it!=v->out.end();++it) {
-		Constraint *c=*it;
-		if(canFollowRight(c,u)) {
-			c->lm=0;
-			reset_active_lm(c->right,v);
-		}
-	}
-	for(Cit it=v->in.begin();it!=v->in.end();++it) {
-		Constraint *c=*it;
-		if(canFollowLeft(c,u)) {
-			c->lm=0;
-			reset_active_lm(c->left,v);
-		}
-	}
+    for(Cit it=v->out.begin();it!=v->out.end();++it) {
+        Constraint *c=*it;
+        if(canFollowRight(c,u)) {
+            c->lm=0;
+            reset_active_lm(c->right,v);
+        }
+    }
+    for(Cit it=v->in.begin();it!=v->in.end();++it) {
+        Constraint *c=*it;
+        if(canFollowLeft(c,u)) {
+            c->lm=0;
+            reset_active_lm(c->left,v);
+        }
+    }
 }
-
+void Block::list_active(Variable* const v, Variable* const u) {
+    for(Cit it=v->out.begin();it!=v->out.end();++it) {
+        Constraint *c=*it;
+        if(canFollowRight(c,u)) {
+#ifdef LIBVPSC_LOGGING
+    ofstream f(LOGFILE,ios::app);
+    f<<"  "<<*c<<endl;
+#endif
+            list_active(c->right,v);
+        }
+    }
+    for(Cit it=v->in.begin();it!=v->in.end();++it) {
+        Constraint *c=*it;
+        if(canFollowLeft(c,u)) {
+#ifdef LIBVPSC_LOGGING
+    ofstream f(LOGFILE,ios::app);
+    f<<"  "<<*c<<endl;
+#endif
+            list_active(c->left,v);
+        }
+    }
+}
+/*
+ * finds the constraint with the minimum lagrange multiplier, that is, the constraint
+ * that most wants to split
+ */
 Constraint *Block::findMinLM() {
-	Constraint *min_lm=NULL;
-	reset_active_lm(vars->front(),NULL);
-	compute_dfdv(vars->front(),NULL,min_lm);
-	return min_lm;
+    Constraint *min_lm=NULL;
+    reset_active_lm(vars->front(),NULL);
+    compute_dfdv(vars->front(),NULL,min_lm);
+#ifdef LIBVPSC_LOGGING
+    ofstream f(LOGFILE,ios::app);
+    f<<"  langrangians: "<<endl;
+    list_active(vars->front(),NULL);
+#endif
+    return min_lm;
 }
 Constraint *Block::findMinLMBetween(Variable* const lv, Variable* const rv) {
-	Constraint *min_lm=NULL;
-	reset_active_lm(vars->front(),NULL);
-	min_lm=compute_dfdv_between(rv,lv,NULL).second;
-	return min_lm;
+    reset_active_lm(vars->front(),NULL);
+    compute_dfdv(vars->front(),NULL);
+    Constraint *min_lm=NULL;
+    split_path(rv,lv,NULL,min_lm);
+#if 0
+    if(min_lm==NULL) {
+        split_path(rv,lv,NULL,min_lm,true);
+    }
+#else
+    if(min_lm==NULL) {
+#ifdef LIBVPSC_DEBUG
+        fprintf(stderr,"Couldn't find split point!\n");
+#endif
+        UnsatisfiableException e;
+        getActivePathBetween(e.path,lv,rv,NULL);
+        throw e;
+    }
+    COLA_ASSERT(min_lm!=NULL);
+#endif
+    return min_lm;
 }
 
 // populates block b by traversing the active constraint tree adding variables as they're 
 // visited.  Starts from variable v and does not backtrack over variable u.
-void Block::populateSplitBlock(Block *b, Variable* const v, Variable* const u) {
-	b->addVariable(v);
-	for (Cit c=v->in.begin();c!=v->in.end();++c) {
-		if (canFollowLeft(*c,u))
-			populateSplitBlock(b, (*c)->left, v);
-	}
-	for (Cit c=v->out.begin();c!=v->out.end();++c) {
-		if (canFollowRight(*c,u)) 
-			populateSplitBlock(b, (*c)->right, v);
-	}
+void Block::populateSplitBlock(Block *b, Variable* v, Variable const* u) {
+    b->addVariable(v);
+    for (Cit c=v->in.begin();c!=v->in.end();++c) {
+        if (canFollowLeft(*c,u))
+            populateSplitBlock(b, (*c)->left, v);
+    }
+    for (Cit c=v->out.begin();c!=v->out.end();++c) {
+        if (canFollowRight(*c,u)) 
+            populateSplitBlock(b, (*c)->right, v);
+    }
+}
+/*
+ * Returns the active path between variables u and v... not back tracking over w
+ */
+bool Block::getActivePathBetween(Constraints& path, Variable const* u,
+               Variable const* v, Variable const *w) const {
+    if(u==v) return true;
+    for (Cit_const c=u->in.begin();c!=u->in.end();++c) {
+        if (canFollowLeft(*c,w)) {
+            if(getActivePathBetween(path, (*c)->left, v, u)) {
+                path.push_back(*c);
+                return true;
+            }
+        }
+    }
+    for (Cit_const c=u->out.begin();c!=u->out.end();++c) {
+        if (canFollowRight(*c,w)) {
+            if(getActivePathBetween(path, (*c)->right, v, u)) {
+                path.push_back(*c);
+                return true;
+            }
+        }
+    }
+    return false;
 }
 // Search active constraint tree from u to see if there is a directed path to v.
 // Returns true if path is found with all constraints in path having their visited flag
 // set true.
-bool Block::isActiveDirectedPathBetween(Variable* u, Variable *v) {
-	if(u==v) return true;
-	for (Cit c=u->out.begin();c!=u->out.end();++c) {
-		if(canFollowRight(*c,NULL)) {
-			if(isActiveDirectedPathBetween((*c)->right,v)) {
-				(*c)->visited=true;
-				return true;
-			}
-			(*c)->visited=false;
-		}
-	}
-	return false;
+bool Block::isActiveDirectedPathBetween(Variable const* u, Variable const* v) const {
+    if(u==v) return true;
+    for (Cit_const c=u->out.begin();c!=u->out.end();++c) {
+        if(canFollowRight(*c,NULL)) {
+            if(isActiveDirectedPathBetween((*c)->right,v)) {
+                return true;
+            }
+        }
+    }
+    return false;
 }
-
+bool Block::getActiveDirectedPathBetween(
+        Constraints& path, Variable const* u, Variable const* v) const {
+    if(u==v) return true;
+    for (Cit_const c=u->out.begin();c!=u->out.end();++c) {
+        if(canFollowRight(*c,NULL)) {
+            if(getActiveDirectedPathBetween(path,(*c)->right,v)) {
+                path.push_back(*c);
+                return true;
+            }
+        }
+    }
+    return false;
+}
+/*
+ * Block needs to be split because of a violated constraint between vl and vr.
+ * We need to search the active constraint tree between l and r and find the constraint
+ * with min lagrangrian multiplier and split at that point.
+ * Returns the split constraint
+ */
 Constraint* Block::splitBetween(Variable* const vl, Variable* const vr,
-	       	Block* &lb, Block* &rb) {
-#ifdef RECTANGLE_OVERLAP_LOGGING
-	ofstream f(LOGFILE,ios::app);
-	f<<"  need to split between: "<<*vl<<" and "<<*vr<<endl;
+               Block* &lb, Block* &rb) {
+#ifdef LIBVPSC_LOGGING
+    ofstream f(LOGFILE,ios::app);
+    f<<"  need to split between: "<<*vl<<" and "<<*vr<<endl;
 #endif
-	Constraint *c=findMinLMBetween(vl, vr);
-#ifdef RECTANGLE_OVERLAP_LOGGING
-	f<<"  going to split on: "<<*c<<endl;
+    Constraint *c=findMinLMBetween(vl, vr);
+#ifdef LIBVPSC_LOGGING
+    f<<"  going to split on: "<<*c<<endl;
 #endif
-	split(lb,rb,c);
-	deleted = true;
-	return c;
+    if(c!=NULL) {
+        split(lb,rb,c);
+        deleted = true;
+    }
+    return c;
 }
 
+/*
+ * Creates two new blocks, l and r, and splits this block across constraint c,
+ * placing the left subtree of constraints (and associated variables) into l
+ * and the right into r.
+ */
 void Block::split(Block* &l, Block* &r, Constraint* c) {
-	c->active=false;
-	l=new Block();
-	populateSplitBlock(l,c->left,c->right);
-	r=new Block();
-	populateSplitBlock(r,c->right,c->left);
+    c->active=false;
+    l=new Block(blocks);
+    populateSplitBlock(l,c->left,c->right);
+    //COLA_ASSERT(l->weight>0);
+    r=new Block(blocks);
+    populateSplitBlock(r,c->right,c->left);
+    //COLA_ASSERT(r->weight>0);
 }
 
+/*
+ * Computes the cost (squared euclidean distance from desired positions) of the
+ * current positions for variables in this block
+ */
 double Block::cost() {
-	double c = 0;
-	for (Vit v=vars->begin();v!=vars->end();++v) {
-		double diff = (*v)->position() - (*v)->desiredPosition;
-		c += (*v)->weight * diff * diff;
-	}
-	return c;
-}
-ostream& operator <<(ostream &os, const Block& b)
+    double c = 0;
+    for (Vit v=vars->begin();v!=vars->end();++v) {
+        double diff = (*v)->position() - (*v)->desiredPosition;
+        c += (*v)->weight * diff * diff;
+    }
+    return c;
+}
+std::ostream& operator <<(std::ostream &os, const Block& b)
 {
-	os<<"Block:";
-	for(Block::Vit v=b.vars->begin();v!=b.vars->end();++v) {
-		os<<" "<<**v;
-	}
-	if(b.deleted) {
-		os<<" Deleted!";
-	}
+    os<<"Block(posn="<<b.posn<<"):";
+    for(Block::Vit v=b.vars->begin();v!=b.vars->end();++v) {
+        os<<" "<<**v;
+    }
+    if(b.deleted) {
+        os<<" Deleted!";
+    }
     return os;
 }
+
 }
+