src/removeoverlap/block.cpp

   1 /**
   2  * \brief Remove overlaps function
   3  *
   4  * Authors:
   5  *   Tim Dwyer <tgdwyer@gmail.com>
   6  *
   7  * Copyright (C) 2005 Authors
   8  *
   9  * Released under GNU GPL.  Read the file 'COPYING' for more information.
  10  */
  11 #include <cassert>
  12 #include "constraint.h"
  13 #include "block.h"
  14 #include "blocks.h"
  15 #include "pairingheap/PairingHeap.h"
  16 #ifdef RECTANGLE_OVERLAP_LOGGING
  17 #include <fstream>
  18 using std::ios;
  19 using std::ofstream;
  20 using std::endl;
  21 #endif
  22 using std::vector;
  23
  24 void Block::addVariable(Variable *v) {
  25         v->block=this;
  26         vars->push_back(v);
  27         weight+=v->weight;
  28         wposn += v->weight * (v->desiredPosition - v->offset);
  29         posn=wposn/weight;
  30 }
  31 Block::Block(Variable *v) {
  32         timeStamp=0;
  33         posn=weight=wposn=0;
  34         in=NULL;
  35         out=NULL;
  36         deleted=false;
  37         vars=new vector<Variable*>;
  38         if(v!=NULL) {
  39                 v->offset=0;
  40                 addVariable(v);
  41         }
  42 }
  43
  44 double Block::desiredWeightedPosition() {
  45         double wp = 0;
  46         for (vector<Variable*>::iterator v=vars->begin();v!=vars->end();v++) {
  47                 wp += ((*v)->desiredPosition - (*v)->offset) * (*v)->weight;
  48         }
  49         return wp;
  50 }
  51 Block::~Block(void)
  52 {
  53         delete vars;
  54         delete in;
  55         delete out;
  56 }
  57 void Block::setUpInConstraints() {
  58         setUpConstraintHeap(in,true);
  59 }
  60 void Block::setUpOutConstraints() {
  61         setUpConstraintHeap(out,false);
  62 }
  63 void Block::setUpConstraintHeap(PairingHeap<Constraint*>* &h,bool in) {
  64         delete h;
  65         h = new PairingHeap<Constraint*>(&compareConstraints);
  66         for (vector<Variable*>::iterator i=vars->begin();i!=vars->end();i++) {
  67                 Variable *v=*i;
  68                 vector<Constraint*> *cs=in?&(v->in):&(v->out);
  69                 for (vector<Constraint*>::iterator j=cs->begin();j!=cs->end();j++) {
  70                         Constraint *c=*j;
  71                         c->timeStamp=blockTimeCtr;
  72                         if (c->left->block != this && in || c->right->block != this && !in) {
  73                                 h->insert(c);
  74                         }
  75                 }
  76         }
  77 }
  78 /**
  79  * Merges b into this block across c.  Can be either a
  80  * right merge or a left merge
  81  * @param b block to merge into this
  82  * @param c constraint being merged
  83  * @param distance separation required to satisfy c
  84  */
  85 void Block::merge(Block *b, Constraint *c, double dist) {
  86         c->active=true;
  87         wposn+=b->wposn-dist*b->weight;
  88         weight+=b->weight;
  89         posn=wposn/weight;
  90         for(vector<Variable*>::iterator i=b->vars->begin();i!=b->vars->end();i++) {
  91                 Variable *v=*i;
  92                 v->block=this;
  93                 v->offset+=dist;
  94                 vars->push_back(v);
  95         }
  96 }
  97
  98 void Block::mergeIn(Block *b) {
  99 #ifdef RECTANGLE_OVERLAP_LOGGING
 100         ofstream f(LOGFILE,ios::app);
 101         f<<"  merging constraint heaps... "<<endl;
 102 #endif
 103         // We check the top of the heaps to remove possible internal constraints
 104         findMinInConstraint();
 105         b->findMinInConstraint();
 106         in->merge(b->in);
 107 #ifdef RECTANGLE_OVERLAP_LOGGING
 108         f<<"  merged heap: "<<*in<<endl;
 109 #endif
 110 }
 111 void Block::mergeOut(Block *b) {
 112         findMinOutConstraint();
 113         b->findMinOutConstraint();
 114         out->merge(b->out);
 115 }
 116 Constraint *Block::findMinInConstraint() {
 117         Constraint *v = NULL;
 118         vector<Constraint*> outOfDate;
 119         while (!in->isEmpty()) {
 120                 v = in->findMin();
 121                 Block *lb=v->left->block;
 122                 Block *rb=v->right->block;
 123                 // rb may not be this if called between merge and mergeIn
 124 #ifdef RECTANGLE_OVERLAP_LOGGING
 125                 ofstream f(LOGFILE,ios::app);
 126                 f<<"  checking constraint ... "<<*v;
 127                 f<<"    timestamps: left="<<lb->timeStamp<<" right="<<rb->timeStamp<<" constraint="<<v->timeStamp<<endl;
 128 #endif
 129                 if(lb == rb) {
 130                         // constraint has been merged into the same block
 131 #ifdef RECTANGLE_OVERLAP_LOGGING
 132                         if(v->slack()<0) {
 133                                 f<<"  violated internal constraint found! "<<*v<<endl;
 134                                 f<<"     lb="<<*lb<<endl;
 135                                 f<<"     rb="<<*rb<<endl;
 136                         }
 137 #endif
 138                         in->deleteMin();
 139 #ifdef RECTANGLE_OVERLAP_LOGGING
 140                         f<<" ... skipping internal constraint"<<endl;
 141 #endif
 142                 } else if(v->timeStamp < lb->timeStamp) {
 143                         // block at other end of constraint has been moved since this
 144                         in->deleteMin();
 145                         outOfDate.push_back(v);
 146 #ifdef RECTANGLE_OVERLAP_LOGGING
 147                         f<<"    reinserting out of date (reinsert later)"<<endl;
 148 #endif
 149                 } else {
 150                         break;
 151                 }
 152         }
 153         for(vector<Constraint*>::iterator i=outOfDate.begin();i!=outOfDate.end();i++) {
 154                 v=*i;
 155                 v->timeStamp=blockTimeCtr;
 156                 in->insert(v);
 157         }
 158         if(in->isEmpty()) {
 159                 v=NULL;
 160         } else {
 161                 v=in->findMin();
 162         }
 163         return v;
 164 }
 165 Constraint *Block::findMinOutConstraint() {
 166         if(out->isEmpty()) return NULL;
 167         Constraint *v = out->findMin();
 168         while (v->left->block == v->right->block) {
 169                 out->deleteMin();
 170                 if(out->isEmpty()) return NULL;
 171                 v = out->findMin();
 172         }
 173         return v;
 174 }
 175 void Block::deleteMinInConstraint() {
 176         in->deleteMin();
 177 #ifdef RECTANGLE_OVERLAP_LOGGING
 178         ofstream f(LOGFILE,ios::app);
 179         f<<"deleteMinInConstraint... "<<endl;
 180         f<<"  result: "<<*in<<endl;
 181 #endif
 182 }
 183 void Block::deleteMinOutConstraint() {
 184         out->deleteMin();
 185 }
 186 inline bool Block::canFollowLeft(Constraint *c, Variable *last) {
 187         return c->left->block==this && c->active && last!=c->left;
 188 }
 189 inline bool Block::canFollowRight(Constraint *c, Variable *last) {
 190         return c->right->block==this && c->active && last!=c->right;
 191 }
 192
 193 // computes the derivative of v and the lagrange multipliers
 194 // of v's out constraints (as the recursive sum of those below.
 195 // Does not backtrack over u.
 196 // also records the constraint with minimum lagrange multiplier
 197 // in min_lm
 198 double Block::compute_dfdv(Variable *v, Variable *u, Constraint *&min_lm) {
 199         double dfdv=v->weight*(v->position() - v->desiredPosition);
 200         for(vector<Constraint*>::iterator it=v->out.begin();it!=v->out.end();it++) {
 201                 Constraint *c=*it;
 202                 if(canFollowRight(c,u)) {
 203                         dfdv+=c->lm=compute_dfdv(c->right,v,min_lm);
 204                         if(min_lm==NULL||c->lm<min_lm->lm) min_lm=c;
 205                 }
 206         }
 207         for(vector<Constraint*>::iterator it=v->in.begin();it!=v->in.end();it++) {
 208                 Constraint *c=*it;
 209                 if(canFollowLeft(c,u)) {
 210                         dfdv-=c->lm=-compute_dfdv(c->left,v,min_lm);
 211                         if(min_lm==NULL||c->lm<min_lm->lm) min_lm=c;
 212                 }
 213         }
 214         return dfdv;
 215 }
 216
 217 // resets LMs for all active constraints to 0 by
 218 // traversing active constraint tree starting from v,
 219 // not back tracking over u
 220 void Block::reset_active_lm(Variable *v, Variable *u) {
 221         for(vector<Constraint*>::iterator it=v->out.begin();it!=v->out.end();it++) {
 222                 Constraint *c=*it;
 223                 if(canFollowRight(c,u)) {
 224                         c->lm=0;
 225                         reset_active_lm(c->right,v);
 226                 }
 227         }
 228         for(vector<Constraint*>::iterator it=v->in.begin();it!=v->in.end();it++) {
 229                 Constraint *c=*it;
 230                 if(canFollowLeft(c,u)) {
 231                         c->lm=0;
 232                         reset_active_lm(c->left,v);
 233                 }
 234         }
 235 }
 236 /**
 237  * finds the constraint with the minimum lagrange multiplier, that is, the constraint
 238  * that most wants to split
 239  */
 240 Constraint *Block::findMinLM() {
 241         Constraint *min_lm=NULL;
 242         reset_active_lm(vars->front(),NULL);
 243         compute_dfdv(vars->front(),NULL,min_lm);
 244         return min_lm;
 245 }
 246
 247 // populates block b by traversing the active constraint tree adding variables as they're
 248 // visited.  Starts from variable v and does not backtrack over variable u.
 249 void Block::populateSplitBlock(Block *b, Variable *v, Variable *u) {
 250         b->addVariable(v);
 251         for (vector<Constraint*>::iterator c=v->in.begin();c!=v->in.end();c++) {
 252                 if (canFollowLeft(*c,u))
 253                         populateSplitBlock(b, (*c)->left, v);
 254         }
 255         for (vector<Constraint*>::iterator c=v->out.begin();c!=v->out.end();c++) {
 256                 if (canFollowRight(*c,u))
 257                         populateSplitBlock(b, (*c)->right, v);
 258         }
 259 }
 260 /**
 261  * Creates two new blocks, l and r, and splits this block across constraint c,
 262  * placing the left subtree of constraints (and associated variables) into l
 263  * and the right into r
 264  */
 265 void Block::split(Block *&l, Block *&r, Constraint *c) {
 266         c->active=false;
 267         l=new Block();
 268         populateSplitBlock(l,c->left,c->right);
 269         r=new Block();
 270         populateSplitBlock(r,c->right,c->left);
 271 }
 272
 273 /**
 274  * Computes the cost (squared euclidean distance from desired positions) of the
 275  * current positions for variables in this block
 276  */
 277 double Block::cost() {
 278         double c = 0;
 279         for (vector<Variable*>::iterator v=vars->begin();v!=vars->end();v++) {
 280                 double diff = (*v)->position() - (*v)->desiredPosition;
 281                 c += (*v)->weight * diff * diff;
 282         }
 283         return c;
 284 }
 285 ostream& operator <<(ostream &os, const Block &b)
 286 {
 287         os<<"Block:";
 288         for(vector<Variable*>::iterator v=b.vars->begin();v!=b.vars->end();v++) {
 289                 os<<" "<<**v;
 290         }
 291     return os;
 292 }