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