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