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