src/removeoverlap/blocks.cpp

   1 /**
   2  * \brief A block structure defined over the variables
   3  *
   4  * A block structure defined over the variables such that each block contains
   5  * 1 or more variables, with the invariant that all constraints inside a block
   6  * are satisfied by keeping the variables fixed relative to one another
   7  *
   8  * Authors:
   9  *   Tim Dwyer <tgdwyer@gmail.com>
  10  *
  11  * Copyright (C) 2005 Authors
  12  *
  13  * Released under GNU GPL.  Read the file 'COPYING' for more information.
  14  */
  15
  16 #include "blocks.h"
  17 #include "block.h"
  18 #include "constraint.h"
  19 #ifdef RECTANGLE_OVERLAP_LOGGING
  20 using std::ios;
  21 using std::ofstream;
  22 using std::endl;
  23 #endif
  24 using std::set;
  25 using std::vector;
  26 using std::iterator;
  27 using std::list;
  28 using std::copy;
  29
  30 long blockTimeCtr;
  31
  32 Blocks::Blocks(Variable *vs[], const int n) : vs(vs),nvs(n) {
  33         blockTimeCtr=0;
  34         for(int i=0;i<nvs;i++) {
  35                 insert(new Block(vs[i]));
  36         }
  37 }
  38 Blocks::~Blocks(void)
  39 {
  40         for(set<Block*>::iterator i=begin();i!=end();i++) {
  41                 delete *i;
  42         }
  43         clear();
  44 }
  45
  46 /**
  47  * returns a list of variables with total ordering determined by the constraint
  48  * DAG
  49  */
  50 list<Variable*> *Blocks::totalOrder() {
  51         list<Variable*> *order = new list<Variable*>;
  52         for(int i=0;i<nvs;i++) {
  53                 vs[i]->visited=false;
  54         }
  55         for(int i=0;i<nvs;i++) {
  56                 if(vs[i]->in.size()==0) {
  57                         dfsVisit(vs[i],order);
  58                 }
  59         }
  60         return order;
  61 }
  62 // Recursive depth first search giving total order by pushing nodes in the DAG
  63 // onto the front of the list when we finish searching them
  64 void Blocks::dfsVisit(Variable *v, list<Variable*> *order) {
  65         v->visited=true;
  66         vector<Constraint*>::iterator it=v->out.begin();
  67         for(;it!=v->out.end();it++) {
  68                 Constraint *c=*it;
  69                 if(!c->right->visited) {
  70                         dfsVisit(c->right, order);
  71                 }
  72         }
  73         order->push_front(v);
  74 }
  75 /**
  76  * Processes incoming constraints, most violated to least, merging with the
  77  * neighbouring (left) block until no more violated constraints are found
  78  */
  79 void Blocks::mergeLeft(Block *r) {
  80 #ifdef RECTANGLE_OVERLAP_LOGGING
  81         ofstream f(LOGFILE,ios::app);
  82         f<<"mergeLeft called on "<<*r<<endl;
  83 #endif
  84         r->timeStamp=++blockTimeCtr;
  85         r->setUpInConstraints();
  86         Constraint *c=r->findMinInConstraint();
  87         while (c != NULL && c->slack()<0) {
  88 #ifdef RECTANGLE_OVERLAP_LOGGING
  89                 f<<"mergeLeft on constraint: "<<*c<<endl;
  90 #endif
  91                 r->deleteMinInConstraint();
  92                 Block *l = c->left->block;
  93                 if (l->in==NULL) l->setUpInConstraints();
  94                 double dist = c->right->offset - c->left->offset - c->gap;
  95                 if (r->vars->size() < l->vars->size()) {
  96                         dist=-dist;
  97                         std::swap(l, r);
  98                 }
  99                 r->merge(l, c, dist);
 100                 r->mergeIn(l);
 101                 r->timeStamp=++blockTimeCtr;
 102                 removeBlock(l);
 103                 c=r->findMinInConstraint();
 104         }
 105 #ifdef RECTANGLE_OVERLAP_LOGGING
 106         f<<"merged "<<*r<<endl;
 107 #endif
 108 }
 109 /**
 110  * Symmetrical to mergeLeft
 111  */
 112 void Blocks::mergeRight(Block *l) {
 113 #ifdef RECTANGLE_OVERLAP_LOGGING
 114         ofstream f(LOGFILE,ios::app);
 115         f<<"mergeRight called on "<<*l<<endl;
 116 #endif
 117         l->setUpOutConstraints();
 118         Constraint *c = l->findMinOutConstraint();
 119         while (c != NULL && c->slack()<0) {
 120 #ifdef RECTANGLE_OVERLAP_LOGGING
 121                 f<<"mergeRight on constraint: "<<*c<<endl;
 122 #endif
 123                 l->deleteMinOutConstraint();
 124                 Block *r = c->right->block;
 125                 r->setUpOutConstraints();
 126                 double dist = c->left->offset + c->gap - c->right->offset;
 127                 if (l->vars->size() > r->vars->size()) {
 128                         dist=-dist;
 129                         std::swap(l, r);
 130                 }
 131                 l->merge(r, c, dist);
 132                 l->mergeOut(r);
 133                 removeBlock(r);
 134                 c=l->findMinOutConstraint();
 135         }
 136 #ifdef RECTANGLE_OVERLAP_LOGGING
 137         f<<"merged "<<*l<<endl;
 138 #endif
 139 }
 140 void Blocks::removeBlock(Block *doomed) {
 141         doomed->deleted=true;
 142         //erase(doomed);
 143 }
 144 void Blocks::cleanup() {
 145         vector<Block*> bcopy(size());
 146         copy(begin(),end(),bcopy.begin());
 147         for(vector<Block*>::iterator i=bcopy.begin();i!=bcopy.end();i++) {
 148                 Block *b=*i;
 149                 if(b->deleted) {
 150                         erase(b);
 151                         delete b;
 152                 }
 153         }
 154 }
 155 /**
 156  * Splits block b across constraint c into two new blocks, l and r (c's left
 157  * and right sides respectively)
 158  */
 159 void Blocks::split(Block *b, Block *&l, Block *&r, Constraint *c) {
 160         b->split(l,r,c);
 161 #ifdef RECTANGLE_OVERLAP_LOGGING
 162         ofstream f(LOGFILE,ios::app);
 163         f<<"Split left: "<<*l<<endl;
 164         f<<"Split right: "<<*r<<endl;
 165 #endif
 166         r->posn = b->posn;
 167         r->wposn = r->posn * r->weight;
 168         mergeLeft(l);
 169         // r may have been merged!
 170         r = c->right->block;
 171         r->wposn = r->desiredWeightedPosition();
 172         r->posn = r->wposn / r->weight;
 173         mergeRight(r);
 174         removeBlock(b);
 175
 176         insert(l);
 177         insert(r);
 178 }
 179 /**
 180  * returns the cost total squared distance of variables from their desired
 181  * positions
 182  */
 183 double Blocks::cost() {
 184         double c = 0;
 185         for(set<Block*>::iterator i=begin();i!=end();i++) {
 186                 c += (*i)->cost();
 187         }
 188         return c;
 189 }
 190