From fd733201b82f39655488a286c89142f321ef9dc9 Mon Sep 17 00:00:00 2001
From: Sylvain Chiron <chironsylvain@orange.fr>
Date: Sat, 1 Jul 2017 13:36:41 +0200
Subject: 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>
---
 src/libvpsc/solve_VPSC.cpp | 812 +++++++++++++++++++++++++++------------------
 1 file changed, 493 insertions(+), 319 deletions(-)

(limited to 'src/libvpsc/solve_VPSC.cpp')

diff --git a/src/libvpsc/solve_VPSC.cpp b/src/libvpsc/solve_VPSC.cpp
index 83cb517b6..aebd0b8d8 100644
--- a/src/libvpsc/solve_VPSC.cpp
+++ b/src/libvpsc/solve_VPSC.cpp
@@ -1,387 +1,561 @@
 /*
- * Solve an instance of the "Variable Placement with Separation
- * Constraints" problem.
+ * vim: ts=4 sw=4 et tw=0 wm=0
  *
- * Authors:
- *   Tim Dwyer <tgdwyer@gmail.com>
+ * libvpsc - A solver for the problem of Variable Placement with 
+ *           Separation Constraints.
  *
- * Copyright (C) 2005 Authors
+ * Copyright (C) 2005-2008  Monash University
  *
- * Released under GNU LGPL.  Read the file 'COPYING' for more information.
- */
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ * See the file LICENSE.LGPL distributed with the library.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ *
+ * Author(s):  Tim Dwyer
+ *             Michael Wybrow
+*/
 
-#include <cassert>
-#include "constraint.h"
-#include "block.h"
-#include "blocks.h"
-#include "solve_VPSC.h"
-#include <math.h>
+#include <cmath>
 #include <sstream>
-#ifdef RECTANGLE_OVERLAP_LOGGING
+#include <map>
+#include <cfloat>
+#include <set>
+
+#include "libvpsc/constraint.h"
+#include "libvpsc/block.h"
+#include "libvpsc/blocks.h"
+#include "libvpsc/solve_VPSC.h"
+#include "libvpsc/cbuffer.h"
+#include "libvpsc/variable.h"
+#include "libvpsc/assertions.h"
+#include "libvpsc/exceptions.h"
+
+#ifdef LIBVPSC_LOGGING
 #include <fstream>
 #endif
-#include <map>
 
 using namespace std;
 
 namespace vpsc {
 
-static const double ZERO_UPPERBOUND=-0.0000001;
+static const double ZERO_UPPERBOUND=-1e-10;
+static const double LAGRANGIAN_TOLERANCE=-1e-4;
 
-IncSolver::IncSolver(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]) 
-	: Solver(n,vs,m,cs) {
-	inactive.assign(cs,cs+m);
-	for(ConstraintList::iterator i=inactive.begin();i!=inactive.end();++i) {
-		(*i)->active=false;
-	}
+IncSolver::IncSolver(Variables const &vs, Constraints const &cs) 
+    : Solver(vs,cs)
+{
+    inactive=cs;
+    for(Constraints::iterator i=inactive.begin();i!=inactive.end();++i) {
+        (*i)->active=false;
+    }
 }
-Solver::Solver(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]) : m(m), cs(cs), n(n), vs(vs) {
-	bs=new Blocks(n, vs);
-#ifdef RECTANGLE_OVERLAP_LOGGING
-	printBlocks();
-	//assert(!constraintGraphIsCyclic(n,vs));
+Solver::Solver(Variables const &vs, Constraints const &cs) 
+    : m(cs.size()), 
+      cs(cs),
+      n(vs.size()),
+      vs(vs),
+      needsScaling(false)
+{
+    for(unsigned i=0;i<n;++i) {
+        vs[i]->in.clear();
+        vs[i]->out.clear();
+
+        // Set needsScaling if any variables have a scale other than 1.
+        needsScaling |= (vs[i]->scale != 1);
+    }
+    for(unsigned i=0;i<m;++i) {
+        Constraint *c=cs[i];
+        c->left->out.push_back(c);
+        c->right->in.push_back(c);
+        c->needsScaling = needsScaling;
+    }
+    bs=new Blocks(vs);
+#ifdef LIBVPSC_LOGGING
+    printBlocks();
+    //COLA_ASSERT(!constraintGraphIsCyclic(n,vs));
 #endif
 }
 Solver::~Solver() {
-	delete bs;
+    delete bs;
+}
+
+void IncSolver::addConstraint(Constraint *c)
+{
+    ++m;
+    c->active = false;
+    inactive.push_back(c);
+    c->left->out.push_back(c);
+    c->right->in.push_back(c);
+    c->needsScaling = needsScaling;
 }
 
 // useful in debugging
 void Solver::printBlocks() {
-#ifdef RECTANGLE_OVERLAP_LOGGING
-	ofstream f(LOGFILE,ios::app);
-	for(set<Block*>::iterator i=bs->begin();i!=bs->end();++i) {
-		Block *b=*i;
-		f<<"  "<<*b<<endl;
-	}
-	for(unsigned i=0;i<m;i++) {
-		f<<"  "<<*cs[i]<<endl;
-	}
+#ifdef LIBVPSC_LOGGING
+    ofstream f(LOGFILE,ios::app);
+    for(set<Block*>::iterator i=bs->begin();i!=bs->end();++i) {
+        Block *b=*i;
+        f<<"  "<<*b<<endl;
+    }
+    for(unsigned i=0;i<m;i++) {
+        f<<"  "<<*cs[i]<<endl;
+    }
 #endif
 }
 
-void Solver::satisfy() {
-	list<Variable*> *vs=bs->totalOrder();
-	for(list<Variable*>::iterator i=vs->begin();i!=vs->end();++i) {
-		Variable *v=*i;
-		if(!v->block->deleted) {
-			bs->mergeLeft(v->block);
-		}
-	}
-	bs->cleanup();
-	for(unsigned i=0;i<m;i++) {
-		if(cs[i]->slack() < ZERO_UPPERBOUND) {
-#ifdef RECTANGLE_OVERLAP_LOGGING
-			ofstream f(LOGFILE,ios::app);
-			f<<"Error: Unsatisfied constraint: "<<*cs[i]<<endl;
+/**
+ * Stores the relative positions of the variables in their finalPosition
+ * field.
+ */
+void Solver::copyResult() {
+    for(Variables::const_iterator i=vs.begin();i!=vs.end();++i) {
+        Variable* v=*i;
+        v->finalPosition=v->position();
+        COLA_ASSERT(v->finalPosition==v->finalPosition);
+    }
+}
+/**
+* Produces a feasible - though not necessarily optimal - solution by
+* examining blocks in the partial order defined by the directed acyclic
+* graph of constraints. For each block (when processing left to right) we
+* maintain the invariant that all constraints to the left of the block
+* (incoming constraints) are satisfied. This is done by repeatedly merging
+* blocks into bigger blocks across violated constraints (most violated
+* first) fixing the position of variables inside blocks relative to one
+* another so that constraints internal to the block are satisfied.
+*/
+bool Solver::satisfy() {
+    list<Variable*> *vList=bs->totalOrder();
+    for(list<Variable*>::iterator i=vList->begin();i!=vList->end();++i) {
+        Variable *v=*i;
+        if(!v->block->deleted) {
+            bs->mergeLeft(v->block);
+        }
+    }
+    bs->cleanup();
+    bool activeConstraints=false;
+    for(unsigned i=0;i<m;i++) {
+        if(cs[i]->active) activeConstraints=true;
+        if(cs[i]->slack() < ZERO_UPPERBOUND) {
+#ifdef LIBVPSC_LOGGING
+            ofstream f(LOGFILE,ios::app);
+            f<<"Error: Unsatisfied constraint: "<<*cs[i]<<endl;
 #endif
-			//assert(cs[i]->slack()>-0.0000001);
-			throw "Unsatisfied constraint";
-		}
-	}
-	delete vs;
+            //COLA_ASSERT(cs[i]->slack()>-0.0000001);
+            throw UnsatisfiedConstraint(*cs[i]);
+        }
+    }
+    delete vList;
+    copyResult();
+    return activeConstraints;
 }
 
 void Solver::refine() {
-	bool solved=false;
-	// Solve shouldn't loop indefinately
-	// ... but just to make sure we limit the number of iterations
-	unsigned maxtries=100;
-	while(!solved&&maxtries>0) {
-		solved=true;
-		maxtries--;
-		for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();++i) {
-			Block *b=*i;
-			b->setUpInConstraints();
-			b->setUpOutConstraints();
-		}
-		for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();++i) {
-			Block *b=*i;
-			Constraint *c=b->findMinLM();
-			if(c!=NULL && c->lm<0) {
-#ifdef RECTANGLE_OVERLAP_LOGGING
-				ofstream f(LOGFILE,ios::app);
-				f<<"Split on constraint: "<<*c<<endl;
+    bool solved=false;
+    // Solve shouldn't loop indefinately
+    // ... but just to make sure we limit the number of iterations
+    unsigned maxtries=100;
+    while(!solved&&maxtries>0) {
+        solved=true;
+        maxtries--;
+        size_t length = bs->size();
+        for (size_t i = 0; i < length; ++i)
+        {
+            Block *b = bs->at(i);
+            b->setUpInConstraints();
+            b->setUpOutConstraints();
+        }
+        for (size_t i = 0; i < length; ++i)
+        {
+            Block *b = bs->at(i);
+            Constraint *c=b->findMinLM();
+            if(c!=NULL && c->lm<LAGRANGIAN_TOLERANCE) {
+#ifdef LIBVPSC_LOGGING
+                ofstream f(LOGFILE,ios::app);
+                f<<"Split on constraint: "<<*c<<endl;
 #endif
-				// Split on c
-				Block *l=NULL, *r=NULL;
-				bs->split(b,l,r,c);
-				bs->cleanup();
-				// split alters the block set so we have to restart
-				solved=false;
-				break;
-			}
-		}
-	}
-	for(unsigned i=0;i<m;i++) {
-		if(cs[i]->slack() < ZERO_UPPERBOUND) {
-			assert(cs[i]->slack()>ZERO_UPPERBOUND);
-			throw "Unsatisfied constraint";
-		}
-	}
+                // Split on c
+                Block *l=NULL, *r=NULL;
+                bs->split(b,l,r,c);
+                bs->cleanup();
+                // split alters the block set so we have to restart
+                solved=false;
+                break;
+            }
+        }
+    }
+    for(unsigned i=0;i<m;i++) {
+        if(cs[i]->slack() < ZERO_UPPERBOUND) {
+            COLA_ASSERT(cs[i]->slack()>ZERO_UPPERBOUND);
+            throw UnsatisfiedConstraint(*cs[i]);
+        }
+    }
 }
-
-void Solver::solve() {
-	satisfy();
-	refine();
+/**
+ * Calculate the optimal solution. After using satisfy() to produce a
+ * feasible solution, refine() examines each block to see if further
+ * refinement is possible by splitting the block. This is done repeatedly
+ * until no further improvement is possible.
+ */
+bool Solver::solve() {
+    satisfy();
+    refine();
+    copyResult();
+    return bs->size()!=n;
 }
 
-void IncSolver::solve() {
-#ifdef RECTANGLE_OVERLAP_LOGGING
-	ofstream f(LOGFILE,ios::app);
-	f<<"solve_inc()..."<<endl;
+bool IncSolver::solve() {
+#ifdef LIBVPSC_LOGGING
+    ofstream f(LOGFILE,ios::app);
+    f<<"solve_inc()..."<<endl;
 #endif
-	double lastcost,cost = bs->cost();
-	do {
-		lastcost=cost;
-		satisfy();
-		splitBlocks();
-		cost = bs->cost();
-#ifdef RECTANGLE_OVERLAP_LOGGING
-	f<<"  cost="<<cost<<endl;
+    satisfy();
+    double lastcost = DBL_MAX, cost = bs->cost();
+    while(fabs(lastcost-cost)>0.0001) {
+        satisfy();
+        lastcost=cost;
+        cost = bs->cost();
+#ifdef LIBVPSC_LOGGING
+        f<<"  bs->size="<<bs->size()<<", cost="<<cost<<endl;
 #endif
-	} while(fabs(lastcost-cost)>0.0001);
+    }
+    copyResult();
+    return bs->size()!=n; 
 }
-
-void IncSolver::satisfy() {
-#ifdef RECTANGLE_OVERLAP_LOGGING
-	ofstream f(LOGFILE,ios::app);
-	f<<"satisfy_inc()..."<<endl;
+/**
+ * incremental version of satisfy that allows refinement after blocks are
+ * moved.
+ *
+ *  - move blocks to new positions
+ *  - repeatedly merge across most violated constraint until no more
+ *    violated constraints exist
+ *
+ * Note: there is a special case to handle when the most violated constraint
+ * is between two variables in the same block.  Then, we must split the block
+ * over an active constraint between the two variables.  We choose the 
+ * constraint with the most negative lagrangian multiplier. 
+ */
+bool IncSolver::satisfy() {
+#ifdef LIBVPSC_LOGGING
+    ofstream f(LOGFILE,ios::app);
+    f<<"satisfy_inc()..."<<endl;
+#endif
+    splitBlocks();
+    //long splitCtr = 0;
+    Constraint* v = NULL;
+    //CBuffer buffer(inactive);
+    while ( (v = mostViolated(inactive)) && 
+            (v->equality || ((v->slack() < ZERO_UPPERBOUND) && !v->active)) ) 
+    {
+        COLA_ASSERT(!v->active);
+        Block *lb = v->left->block, *rb = v->right->block;
+        if(lb != rb) {
+            lb->merge(rb,v);
+        } else {
+            if(lb->isActiveDirectedPathBetween(v->right,v->left)) {
+                // cycle found, relax the violated, cyclic constraint
+                v->unsatisfiable=true;
+                continue;
+                //UnsatisfiableException e;
+                //lb->getActiveDirectedPathBetween(e.path,v->right,v->left);
+                //e.path.push_back(v);
+                //throw e;
+            }
+            //if(splitCtr++>10000) {
+                //throw "Cycle Error!";
+            //}
+            // constraint is within block, need to split first
+            try {
+                Constraint* splitConstraint
+                    =lb->splitBetween(v->left,v->right,lb,rb);
+                if(splitConstraint!=NULL) {
+                    COLA_ASSERT(!splitConstraint->active);
+                    inactive.push_back(splitConstraint);
+                } else {
+                    v->unsatisfiable=true;
+                    continue;
+                }
+            } catch(UnsatisfiableException e) {
+                e.path.push_back(v);
+#ifdef LIBVPSC_DEBUG
+                std::cerr << "Unsatisfiable:" << std::endl;
+                for(std::vector<Constraint*>::iterator r=e.path.begin();
+                        r!=e.path.end();++r)
+                {
+                    std::cerr << **r <<std::endl;
+                }
 #endif
-	splitBlocks();
-	long splitCtr = 0;
-	Constraint* v = NULL;
-	while((v=mostViolated(inactive))&&(v->equality || v->slack() < ZERO_UPPERBOUND)) {
-		assert(!v->active);
-		Block *lb = v->left->block, *rb = v->right->block;
-		if(lb != rb) {
-			lb->merge(rb,v);
-		} else {
-			if(lb->isActiveDirectedPathBetween(v->right,v->left)) {
-				// cycle found, relax the violated, cyclic constraint
-				v->gap = v->slack();
-				continue;
-			}
-			if(splitCtr++>10000) {
-				throw "Cycle Error!";
-			}
-			// constraint is within block, need to split first
-			inactive.push_back(lb->splitBetween(v->left,v->right,lb,rb));
-			lb->merge(rb,v);
-			bs->insert(lb);
-		}
-	}
-#ifdef RECTANGLE_OVERLAP_LOGGING
-	f<<"  finished merges."<<endl;
+                v->unsatisfiable=true;
+                continue;
+            }
+            if(v->slack()>=0) {
+                COLA_ASSERT(!v->active);
+                // v was satisfied by the above split!
+                inactive.push_back(v);
+                bs->insert(lb);
+                bs->insert(rb);
+            } else {
+                bs->insert(lb->merge(rb,v));
+                delete ((lb->deleted) ? lb : rb);
+            }
+        }
+#ifdef LIBVPSC_LOGGING
+        f<<"...remaining blocks="<<bs->size()<<", cost="<<bs->cost()<<endl;
 #endif
-	bs->cleanup();
-	for(unsigned i=0;i<m;i++) {
-		v=cs[i];
-		if(v->slack() < ZERO_UPPERBOUND) {
-			ostringstream s;
-			s<<"Unsatisfied constraint: "<<*v;
-#ifdef RECTANGLE_OVERLAP_LOGGING
-			ofstream f(LOGFILE,ios::app);
-			f<<s.str()<<endl;
+    }
+#ifdef LIBVPSC_LOGGING
+    f<<"  finished merges."<<endl;
 #endif
-			throw s.str().c_str();
-		}
-	}
-#ifdef RECTANGLE_OVERLAP_LOGGING
-	f<<"  finished cleanup."<<endl;
-	printBlocks();
+    bs->cleanup();
+    bool activeConstraints=false;
+    for(unsigned i=0;i<m;i++) {
+        v=cs[i];
+        if(v->active) activeConstraints=true;
+        if(v->slack() < ZERO_UPPERBOUND) {
+            ostringstream s;
+            s<<"Unsatisfied constraint: "<<*v;
+#ifdef LIBVPSC_LOGGING
+            ofstream f(LOGFILE,ios::app);
+            f<<s.str()<<endl;
 #endif
+            throw (char *) s.str().c_str();
+        }
+    }
+#ifdef LIBVPSC_LOGGING
+    f<<"  finished cleanup."<<endl;
+    printBlocks();
+#endif
+    copyResult();
+    return activeConstraints;
 }
 void IncSolver::moveBlocks() {
-#ifdef RECTANGLE_OVERLAP_LOGGING
-	ofstream f(LOGFILE,ios::app);
-	f<<"moveBlocks()..."<<endl;
+#ifdef LIBVPSC_LOGGING
+    ofstream f(LOGFILE,ios::app);
+    f<<"moveBlocks()..."<<endl;
 #endif
-	for(set<Block*>::const_iterator i(bs->begin());i!=bs->end();++i) {
-		Block *b = *i;
-		b->wposn = b->desiredWeightedPosition();
-		b->posn = b->wposn / b->weight;
-	}
-#ifdef RECTANGLE_OVERLAP_LOGGING
-	f<<"  moved blocks."<<endl;
+    size_t length = bs->size();
+    for (size_t i = 0; i < length; ++i)
+    {
+        Block *b = bs->at(i);
+        b->updateWeightedPosition();
+        //b->posn = b->wposn / b->weight;
+    }
+#ifdef LIBVPSC_LOGGING
+    f<<"  moved blocks."<<endl;
 #endif
 }
 void IncSolver::splitBlocks() {
-#ifdef RECTANGLE_OVERLAP_LOGGING
-	ofstream f(LOGFILE,ios::app);
+#ifdef LIBVPSC_LOGGING
+    ofstream f(LOGFILE,ios::app);
 #endif
-	moveBlocks();
-	splitCnt=0;
-	// Split each block if necessary on min LM
-	for(set<Block*>::const_iterator i(bs->begin());i!=bs->end();++i) {
-		Block* b = *i;
-		Constraint* v=b->findMinLM();
-		if(v!=NULL && v->lm < ZERO_UPPERBOUND) {
-			assert(!v->equality);
-#ifdef RECTANGLE_OVERLAP_LOGGING
-			f<<"    found split point: "<<*v<<" lm="<<v->lm<<endl;
+    moveBlocks();
+    splitCnt=0;
+    // Split each block if necessary on min LM
+    size_t length = bs->size();
+    for (size_t i = 0; i < length; ++i)
+    {
+        Block *b = bs->at(i);
+        Constraint* v=b->findMinLM();
+        if(v!=NULL && v->lm < LAGRANGIAN_TOLERANCE) {
+            COLA_ASSERT(!v->equality);
+#ifdef LIBVPSC_LOGGING
+            f<<"    found split point: "<<*v<<" lm="<<v->lm<<endl;
 #endif
-			splitCnt++;
-			Block *b = v->left->block, *l=NULL, *r=NULL;
-			assert(v->left->block == v->right->block);
-			double pos = b->posn;
-			b->split(l,r,v);
-			l->posn=r->posn=pos;
-			l->wposn = l->posn * l->weight;
-			r->wposn = r->posn * r->weight;
-			bs->insert(l);
-			bs->insert(r);
-			b->deleted=true;
-			inactive.push_back(v);
-#ifdef RECTANGLE_OVERLAP_LOGGING
-			f<<"  new blocks: "<<*l<<" and "<<*r<<endl;
+            splitCnt++;
+            Block *b = v->left->block, *l=NULL, *r=NULL;
+            COLA_ASSERT(v->left->block == v->right->block);
+            //double pos = b->posn;
+            b->split(l,r,v);
+            //l->posn=r->posn=pos;
+            //l->wposn = l->posn * l->weight;
+            //r->wposn = r->posn * r->weight;
+            l->updateWeightedPosition();
+            r->updateWeightedPosition();
+            bs->insert(l);
+            bs->insert(r);
+            b->deleted=true;
+            COLA_ASSERT(!v->active);
+            inactive.push_back(v);
+#ifdef LIBVPSC_LOGGING
+            f<<"  new blocks: "<<*l<<" and "<<*r<<endl;
 #endif
-		}
-	}
-#ifdef RECTANGLE_OVERLAP_LOGGING
-	f<<"  finished splits."<<endl;
+        }
+    }
+    //if(splitCnt>0) { std::cout<<"  splits: "<<splitCnt<<endl; }
+#ifdef LIBVPSC_LOGGING
+    f<<"  finished splits."<<endl;
 #endif
-	bs->cleanup();
+    bs->cleanup();
 }
 
-Constraint* IncSolver::mostViolated(ConstraintList &l) {
-	double minSlack = DBL_MAX;
-	Constraint* v=NULL;
-#ifdef RECTANGLE_OVERLAP_LOGGING
-	ofstream f(LOGFILE,ios::app);
-	f<<"Looking for most violated..."<<endl;
+/**
+ * Scan constraint list for the most violated constraint, or the first equality
+ * constraint
+ */
+Constraint* IncSolver::mostViolated(Constraints &l)
+{
+    double slackForMostViolated = DBL_MAX;
+    Constraint* mostViolated = NULL;
+#ifdef LIBVPSC_LOGGING
+    ofstream f(LOGFILE,ios::app);
+    f << "Looking for most violated..." << endl;
 #endif
-	ConstraintList::iterator end = l.end();
-	ConstraintList::iterator deletePoint = end;
-	for(ConstraintList::iterator i=l.begin();i!=end;++i) {
-		Constraint *c=*i;
-		double slack = c->slack();
-		if(c->equality || slack < minSlack) {
-			minSlack=slack;	
-			v=c;
-			deletePoint=i;
-			if(c->equality) break;
-		}
-	}
-	// Because the constraint list is not order dependent we just
-	// move the last element over the deletePoint and resize
-	// downwards.  There is always at least 1 element in the
-	// vector because of search.
-	if(deletePoint != end && (minSlack<ZERO_UPPERBOUND||v->equality)) {
-		*deletePoint = l[l.size()-1];
-		l.resize(l.size()-1);
-	}
-#ifdef RECTANGLE_OVERLAP_LOGGING
-	f<<"  most violated is: "<<*v<<endl;
+    size_t lSize = l.size();
+    size_t deleteIndex = lSize;
+    Constraint *constraint = NULL;
+    double slack = 0;
+    for (size_t index = 0; index < lSize; ++index)
+    {
+        constraint = l[index];
+        slack = constraint->slack();
+        if (constraint->equality || slack < slackForMostViolated)
+        {
+            slackForMostViolated = slack;    
+            mostViolated = constraint;
+            deleteIndex = index;
+            if (constraint->equality)
+            {
+                break;
+            }
+        }
+    }
+    // Because the constraint list is not order dependent we just
+    // move the last element over the deletePoint and resize
+    // downwards.  There is always at least 1 element in the
+    // vector because of search.
+    if ( (deleteIndex < lSize) && 
+         (((slackForMostViolated < ZERO_UPPERBOUND) && !mostViolated->active) || 
+          mostViolated->equality) )
+    {
+        l[deleteIndex] = l[lSize-1];
+        l.resize(lSize-1);
+    }
+#ifdef LIBVPSC_LOGGING
+    if (mostViolated)
+    {
+        f << "  most violated is: " << *mostViolated << endl;
+    }
+    else
+    {
+        f << "  non found." << endl;
+    }
 #endif
-	return v;
+    return mostViolated;
 }
 
 struct node {
-	set<node*> in;
-	set<node*> out;
+    set<node*> in;
+    set<node*> out;
 };
 // useful in debugging - cycles would be BAD
 bool Solver::constraintGraphIsCyclic(const unsigned n, Variable* const vs[]) {
-	map<Variable*, node*> varmap;
-	vector<node*> graph;
-	for(unsigned i=0;i<n;i++) {
-		node *u=new node;
-		graph.push_back(u);
-		varmap[vs[i]]=u;
-	}
-	for(unsigned i=0;i<n;i++) {
-		for(vector<Constraint*>::iterator c=vs[i]->in.begin();c!=vs[i]->in.end();++c) {
-			Variable *l=(*c)->left;
-			varmap[vs[i]]->in.insert(varmap[l]);
-		}
+    map<Variable*, node*> varmap;
+    vector<node*> graph;
+    for(unsigned i=0;i<n;i++) {
+        node *u=new node;
+        graph.push_back(u);
+        varmap[vs[i]]=u;
+    }
+    for(unsigned i=0;i<n;i++) {
+        for(vector<Constraint*>::iterator c=vs[i]->in.begin();c!=vs[i]->in.end();++c) {
+            Variable *l=(*c)->left;
+            varmap[vs[i]]->in.insert(varmap[l]);
+        }
 
-		for(vector<Constraint*>::iterator c=vs[i]->out.begin();c!=vs[i]->out.end();++c) {
-			Variable *r=(*c)->right;
-			varmap[vs[i]]->out.insert(varmap[r]);
-		}
-	}
-	while(!graph.empty()) {
-		node *u=NULL;
-		vector<node*>::iterator i=graph.begin();
-		for(;i!=graph.end();++i) {
-			u=*i;
-			if(u->in.empty()) {
-				break;
-			}
-		}
-		if(i==graph.end() && !graph.empty()) {
-			//cycle found!
-			return true;
-		} else {
-			graph.erase(i);
-			for(set<node*>::iterator j=u->out.begin();j!=u->out.end();++j) {
-				node *v=*j;
-				v->in.erase(u);
-			}
-			delete u;
-		}
-	}
-	for(unsigned i=0; i<graph.size(); ++i) {
-		delete graph[i];
-	}
-	return false;
+        for(vector<Constraint*>::iterator c=vs[i]->out.begin();c!=vs[i]->out.end();++c) {
+            Variable *r=(*c)->right;
+            varmap[vs[i]]->out.insert(varmap[r]);
+        }
+    }
+    while(graph.size()>0) {
+        node *u=NULL;
+        vector<node*>::iterator i=graph.begin();
+        for(;i!=graph.end();++i) {
+            u=*i;
+            if(u->in.size()==0) {
+                break;
+            }
+        }
+        if(i==graph.end() && graph.size()>0) {
+            //cycle found!
+            return true;
+        } else {
+            graph.erase(i);
+            for(set<node*>::iterator j=u->out.begin();j!=u->out.end();++j) {
+                node *v=*j;
+                v->in.erase(u);
+            }
+            delete u;
+        }
+    }
+    for(unsigned i=0; i<graph.size(); ++i) {
+        delete graph[i];
+    }
+    return false;
 }
 
 // useful in debugging - cycles would be BAD
 bool Solver::blockGraphIsCyclic() {
-	map<Block*, node*> bmap;
-	vector<node*> graph;
-	for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();++i) {
-		Block *b=*i;
-		node *u=new node;
-		graph.push_back(u);
-		bmap[b]=u;
-	}
-	for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();++i) {
-		Block *b=*i;
-		b->setUpInConstraints();
-		Constraint *c=b->findMinInConstraint();
-		while(c!=NULL) {
-			Block *l=c->left->block;
-			bmap[b]->in.insert(bmap[l]);
-			b->deleteMinInConstraint();
-			c=b->findMinInConstraint();
-		}
+    map<Block*, node*> bmap;
+    vector<node*> graph;
+    size_t length = bs->size();
+    for (size_t i = 0; i < length; ++i)
+    {
+        Block *b = bs->at(i);
+        node *u=new node;
+        graph.push_back(u);
+        bmap[b]=u;
+    }
+    for (size_t i = 0; i < length; ++i)
+    {
+        Block *b = bs->at(i);
+        b->setUpInConstraints();
+        Constraint *c=b->findMinInConstraint();
+        while(c!=NULL) {
+            Block *l=c->left->block;
+            bmap[b]->in.insert(bmap[l]);
+            b->deleteMinInConstraint();
+            c=b->findMinInConstraint();
+        }
 
-		b->setUpOutConstraints();
-		c=b->findMinOutConstraint();
-		while(c!=NULL) {
-			Block *r=c->right->block;
-			bmap[b]->out.insert(bmap[r]);
-			b->deleteMinOutConstraint();
-			c=b->findMinOutConstraint();
-		}
-	}
-	while(!graph.empty()) {
-		node *u=NULL;
-		vector<node*>::iterator i=graph.begin();
-		for(;i!=graph.end();++i) {
-			u=*i;
-			if(u->in.empty()) {
-				break;
-			}
-		}
-		if(i==graph.end() && !graph.empty()) {
-			//cycle found!
-			return true;
-		} else {
-			graph.erase(i);
-			for(set<node*>::iterator j=u->out.begin();j!=u->out.end();++j) {
-				node *v=*j;
-				v->in.erase(u);
-			}
-			delete u;
-		}
-	}
-	for(unsigned i=0; i<graph.size(); i++) {
-		delete graph[i];
-	}
-	return false;
+        b->setUpOutConstraints();
+        c=b->findMinOutConstraint();
+        while(c!=NULL) {
+            Block *r=c->right->block;
+            bmap[b]->out.insert(bmap[r]);
+            b->deleteMinOutConstraint();
+            c=b->findMinOutConstraint();
+        }
+    }
+    while(graph.size()>0) {
+        node *u=NULL;
+        vector<node*>::iterator i=graph.begin();
+        for(;i!=graph.end();++i) {
+            u=*i;
+            if(u->in.size()==0) {
+                break;
+            }
+        }
+        if(i==graph.end() && graph.size()>0) {
+            //cycle found!
+            return true;
+        } else {
+            graph.erase(i);
+            for(set<node*>::iterator j=u->out.begin();j!=u->out.end();++j) {
+                node *v=*j;
+                v->in.erase(u);
+            }
+            delete u;
+        }
+    }
+    for(unsigned i=0; i<graph.size(); i++) {
+        delete graph[i];
+    }
+    return false;
 }
 }
-- 
cgit v1.2.3