blocks.cpp

/**
 * \brief A block structure defined over the variables
 *
 * A block structure defined over the variables such that each block contains
 * 1 or more variables, with the invariant that all constraints inside a block
 * are satisfied by keeping the variables fixed relative to one another
 *
 * Authors:
 *   Tim Dwyer <tgdwyer@gmail.com>
 *
 * Copyright (C) 2005 Authors
 *
 * Released under GNU LGPL.  Read the file 'COPYING' for more information.
 */

#include "blocks.h"
#include "block.h"
#include "constraint.h"
#ifdef RECTANGLE_OVERLAP_LOGGING
#include <fstream>
using std::ios;
using std::ofstream;
using std::endl;
#endif
using std::set;
using std::vector;
using std::iterator;
using std::list;
using std::copy;

namespace vpsc {

long blockTimeCtr;

Blocks::Blocks(const int n, Variable* const vs[]) : vs(vs),nvs(n) {
      blockTimeCtr=0;
      for(int i=0;i<nvs;i++) {
            insert(new Block(vs[i]));
      }
}
Blocks::~Blocks(void)
{
      blockTimeCtr=0;
      for(set<Block*>::iterator i=begin();i!=end();++i) {
            delete *i;
      }
      clear();
}

/**
 * returns a list of variables with total ordering determined by the constraint 
 * DAG
 */
00054 list<Variable*> *Blocks::totalOrder() {
      list<Variable*> *order = new list<Variable*>;
      for(int i=0;i<nvs;i++) {
            vs[i]->visited=false;
      }
      for(int i=0;i<nvs;i++) {
            if(vs[i]->in.size()==0) {
                  dfsVisit(vs[i],order);
            }
      }
      return order;
}
// Recursive depth first search giving total order by pushing nodes in the DAG
// onto the front of the list when we finish searching them
void Blocks::dfsVisit(Variable *v, list<Variable*> *order) {
      v->visited=true;
      vector<Constraint*>::iterator it=v->out.begin();
      for(;it!=v->out.end();++it) {
            Constraint *c=*it;
            if(!c->right->visited) {
                  dfsVisit(c->right, order);
            }
      }     
#ifdef RECTANGLE_OVERLAP_LOGGING
      ofstream f(LOGFILE,ios::app);
      f<<"  order="<<*v<<endl;
#endif
      order->push_front(v);
}
/**
 * Processes incoming constraints, most violated to least, merging with the
 * neighbouring (left) block until no more violated constraints are found
 */
00087 void Blocks::mergeLeft(Block *r) {  
#ifdef RECTANGLE_OVERLAP_LOGGING
      ofstream f(LOGFILE,ios::app);
      f<<"mergeLeft called on "<<*r<<endl;
#endif
      r->timeStamp=++blockTimeCtr;
      r->setUpInConstraints();
      Constraint *c=r->findMinInConstraint();
      while (c != NULL && c->slack()<0) {
#ifdef RECTANGLE_OVERLAP_LOGGING
            f<<"mergeLeft on constraint: "<<*c<<endl;
#endif
            r->deleteMinInConstraint();
            Block *l = c->left->block;          
            if (l->in==NULL) l->setUpInConstraints();
            double dist = c->right->offset - c->left->offset - c->gap;
            if (r->vars->size() < l->vars->size()) {
                  dist=-dist;
                  std::swap(l, r);
            }
            blockTimeCtr++;
            r->merge(l, c, dist);
            r->mergeIn(l);
            r->timeStamp=blockTimeCtr;
            removeBlock(l);
            c=r->findMinInConstraint();
      }           
#ifdef RECTANGLE_OVERLAP_LOGGING
      f<<"merged "<<*r<<endl;
#endif
}     
/**
 * Symmetrical to mergeLeft
 */
00121 void Blocks::mergeRight(Block *l) { 
#ifdef RECTANGLE_OVERLAP_LOGGING
      ofstream f(LOGFILE,ios::app);
      f<<"mergeRight called on "<<*l<<endl;
#endif      
      l->setUpOutConstraints();
      Constraint *c = l->findMinOutConstraint();
      while (c != NULL && c->slack()<0) {       
#ifdef RECTANGLE_OVERLAP_LOGGING
            f<<"mergeRight on constraint: "<<*c<<endl;
#endif
            l->deleteMinOutConstraint();
            Block *r = c->right->block;
            r->setUpOutConstraints();
            double dist = c->left->offset + c->gap - c->right->offset;
            if (l->vars->size() > r->vars->size()) {
                  dist=-dist;
                  std::swap(l, r);
            }
            l->merge(r, c, dist);
            l->mergeOut(r);
            removeBlock(r);
            c=l->findMinOutConstraint();
      }     
#ifdef RECTANGLE_OVERLAP_LOGGING
      f<<"merged "<<*l<<endl;
#endif
}
void Blocks::removeBlock(Block *doomed) {
      doomed->deleted=true;
      //erase(doomed);
}
void Blocks::cleanup() {
      vector<Block*> bcopy(begin(),end());
      for(vector<Block*>::iterator i=bcopy.begin();i!=bcopy.end();++i) {
            Block *b=*i;
            if(b->deleted) {
                  erase(b);
                  delete b;
            }
      }
}
/**
 * Splits block b across constraint c into two new blocks, l and r (c's left
 * and right sides respectively)
 */
00167 void Blocks::split(Block *b, Block *&l, Block *&r, Constraint *c) {
      b->split(l,r,c);
#ifdef RECTANGLE_OVERLAP_LOGGING
      ofstream f(LOGFILE,ios::app);
      f<<"Split left: "<<*l<<endl;
      f<<"Split right: "<<*r<<endl;
#endif
      r->posn = b->posn;
      r->wposn = r->posn * r->weight;
      mergeLeft(l);
      // r may have been merged!
      r = c->right->block;
      r->wposn = r->desiredWeightedPosition();
      r->posn = r->wposn / r->weight;
      mergeRight(r);
      removeBlock(b);

      insert(l);
      insert(r);
}
/**
 * returns the cost total squared distance of variables from their desired
 * positions
 */
00191 double Blocks::cost() {
      double c = 0;
      for(set<Block*>::iterator i=begin();i!=end();++i) {
            c += (*i)->cost();
      }
      return c;
}

}