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
  12
  13 #include "constraint.h"
  14 #include "block.h"
  15 #include "blocks.h"
  16 #include "pairingheap/PairingHeap.h"
  17 #ifdef RECTANGLE_OVERLAP_LOGGING
  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 }
 108 void Block::mergeOut(Block *b) {
 109         findMinOutConstraint();
 110         b->findMinOutConstraint();
 111         out->merge(b->out);
 112 }
 113 Constraint *Block::findMinInConstraint() {
 114         Constraint *v = NULL;
 115         vector<Constraint*> outOfDate;
 116         while (!in->isEmpty()) {
 117                 v = in->findMin();
 118                 Block *lb=v->left->block;
 119                 Block *rb=v->right->block;
 120                 // rb may not be this if called between merge and mergeIn
 121 #ifdef RECTANGLE_OVERLAP_LOGGING
 122                 ofstream f(LOGFILE,ios::app);
 123                 f<<"  checking constraint ... "<<*v;
 124                 f<<"    timestamps: left="<<lb->timeStamp<<" right="<<rb->timeStamp<<" constraint="<<v->timeStamp<<endl;
 125 #endif
 126                 if(lb == rb) {
 127                         // constraint has been merged into the same block
 128                         in->deleteMin();
 129 #ifdef RECTANGLE_OVERLAP_LOGGING
 130                         f<<" ... skipping internal constraint"<<endl;
 131 #endif
 132                 } else if(lb->timeStamp > rb->timeStamp
 133                         && v->timeStamp < lb->timeStamp
 134                         || v->timeStamp < rb->timeStamp) {
 135                         // block at other end of constraint has been moved since this
 136                         in->deleteMin();
 137                         outOfDate.push_back(v);
 138 #ifdef RECTANGLE_OVERLAP_LOGGING
 139                         f<<"    reinserting out of date constraint"<<endl;
 140 #endif
 141                 } else {
 142                         break;
 143                 }
 144         }
 145         for(vector<Constraint*>::iterator i=outOfDate.begin();i!=outOfDate.end();i++) {
 146                 v=*i;
 147                 v->timeStamp=blockTimeCtr;
 148                 in->insert(v);
 149         }
 150         if(in->isEmpty()) {
 151                 v=NULL;
 152         } else {
 153                 v=in->findMin();
 154         }
 155         return v;
 156 }
 157 Constraint *Block::findMinOutConstraint() {
 158         if(out->isEmpty()) return NULL;
 159         Constraint *v = out->findMin();
 160         while (v->left->block == v->right->block) {
 161                 out->deleteMin();
 162                 if(out->isEmpty()) return NULL;
 163                 v = out->findMin();
 164         }
 165         return v;
 166 }
 167 void Block::deleteMinInConstraint() {
 168         in->deleteMin();
 169 }
 170 void Block::deleteMinOutConstraint() {
 171         out->deleteMin();
 172 }
 173 inline bool Block::canFollowLeft(Constraint *c, Variable *last) {
 174         return c->left->block==this && c->active && last!=c->left;
 175 }
 176 inline bool Block::canFollowRight(Constraint *c, Variable *last) {
 177         return c->right->block==this && c->active && last!=c->right;
 178 }
 179
 180 // computes the derivative of v and the lagrange multipliers
 181 // of v's out constraints (as the recursive sum of those below.
 182 // Does not backtrack over u.
 183 // also records the constraint with minimum lagrange multiplier
 184 // in min_lm
 185 double Block::compute_dfdv(Variable *v, Variable *u, Constraint *&min_lm) {
 186         double dfdv=v->weight*(v->position() - v->desiredPosition);
 187         for(vector<Constraint*>::iterator it=v->out.begin();it!=v->out.end();it++) {
 188                 Constraint *c=*it;
 189                 if(canFollowRight(c,u)) {
 190                         dfdv+=c->lm=compute_dfdv(c->right,v,min_lm);
 191                         if(min_lm==NULL||c->lm<min_lm->lm) min_lm=c;
 192                 }
 193         }
 194         for(vector<Constraint*>::iterator it=v->in.begin();it!=v->in.end();it++) {
 195                 Constraint *c=*it;
 196                 if(canFollowLeft(c,u)) {
 197                         dfdv-=c->lm=-compute_dfdv(c->left,v,min_lm);
 198                         if(min_lm==NULL||c->lm<min_lm->lm) min_lm=c;
 199                 }
 200         }
 201         return dfdv;
 202 }
 203
 204 // resets LMs for all active constraints to 0 by
 205 // traversing active constraint tree starting from v,
 206 // not back tracking over u
 207 void Block::reset_active_lm(Variable *v, Variable *u) {
 208         for(vector<Constraint*>::iterator it=v->out.begin();it!=v->out.end();it++) {
 209                 Constraint *c=*it;
 210                 if(canFollowRight(c,u)) {
 211                         c->lm=0;
 212                         reset_active_lm(c->right,v);
 213                 }
 214         }
 215         for(vector<Constraint*>::iterator it=v->in.begin();it!=v->in.end();it++) {
 216                 Constraint *c=*it;
 217                 if(canFollowLeft(c,u)) {
 218                         c->lm=0;
 219                         reset_active_lm(c->left,v);
 220                 }
 221         }
 222 }
 223 /**
 224  * finds the constraint with the minimum lagrange multiplier, that is, the constraint
 225  * that most wants to split
 226  */
 227 Constraint *Block::findMinLM() {
 228         Constraint *min_lm=NULL;
 229         reset_active_lm(vars->front(),NULL);
 230         compute_dfdv(vars->front(),NULL,min_lm);
 231         return min_lm;
 232 }
 233
 234 // populates block b by traversing the active constraint tree adding variables as they're
 235 // visited.  Starts from variable v and does not backtrack over variable u.
 236 void Block::populateSplitBlock(Block *b, Variable *v, Variable *u) {
 237         b->addVariable(v);
 238         for (vector<Constraint*>::iterator c=v->in.begin();c!=v->in.end();c++) {
 239                 if (canFollowLeft(*c,u))
 240                         populateSplitBlock(b, (*c)->left, v);
 241         }
 242         for (vector<Constraint*>::iterator c=v->out.begin();c!=v->out.end();c++) {
 243                 if (canFollowRight(*c,u))
 244                         populateSplitBlock(b, (*c)->right, v);
 245         }
 246 }
 247 /**
 248  * Creates two new blocks, l and r, and splits this block across constraint c,
 249  * placing the left subtree of constraints (and associated variables) into l
 250  * and the right into r
 251  */
 252 void Block::split(Block *&l, Block *&r, Constraint *c) {
 253         c->active=false;
 254         l=new Block();
 255         populateSplitBlock(l,c->left,c->right);
 256         r=new Block();
 257         populateSplitBlock(r,c->right,c->left);
 258 }
 259
 260 /**
 261  * Computes the cost (squared euclidean distance from desired positions) of the
 262  * current positions for variables in this block
 263  */
 264 double Block::cost() {
 265         double c = 0;
 266         for (vector<Variable*>::iterator v=vars->begin();v!=vars->end();v++) {
 267                 double diff = (*v)->position() - (*v)->desiredPosition;
 268                 c += (*v)->weight * diff * diff;
 269         }
 270         return c;
 271 }
 272 ostream& operator <<(ostream &os, const Block &b)
 273 {
 274         os<<"Block:";
 275         for(vector<Variable*>::iterator v=b.vars->begin();v!=b.vars->end();v++) {
 276                 os<<" "<<**v;
 277         }
 278     return os;
 279 }