blocks.cpp

Go to the documentation of this file.

 
#include "config.h"
 
#include <vpsc/blocks.h>
#include <vpsc/block.h>
#include <vpsc/constraint.h>
#include <fstream>
using std::ios;
using std::ofstream;
using std::set;
using std::list;
 
#ifndef RECTANGLE_OVERLAP_LOGGING
        #define RECTANGLE_OVERLAP_LOGGING 0
#endif
 
long blockTimeCtr;
 
Blocks::Blocks(const int n, Variable *vs_[]) : vs(vs_), nvs(n) {
        blockTimeCtr=0;
        for(int i=0;i<nvs;i++) {
                insert(new Block(vs[i]));
        }
}
Blocks::~Blocks()
{
        blockTimeCtr=0;
        for (Block *b : *this) {
                delete b;
        }
}
 
list<Variable*> Blocks::totalOrder() {
        list<Variable*> order;
        for(int i=0;i<nvs;i++) {
                vs[i]->visited=false;
        }
        for(int i=0;i<nvs;i++) {
                if(vs[i]->in.empty()) {
                        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;
        for (Constraint *c : v->out) {
                if(!c->right->visited) {
                        dfsVisit(c->right, order);
                }
        }       
        if (RECTANGLE_OVERLAP_LOGGING) {
                ofstream f(LOGFILE,ios::app);
                f<<"  order="<<*v<<"\n";
        }
        order.push_front(v);
}
void Blocks::mergeLeft(Block *r) {      
        if (RECTANGLE_OVERLAP_LOGGING) {
                ofstream f(LOGFILE,ios::app);
                f<<"mergeLeft called on "<<*r<<"\n";
        }
        r->timeStamp=++blockTimeCtr;
        r->setUpInConstraints();
        Constraint *c=r->findMinInConstraint();
        while (c != nullptr && c->slack()<0) {
                if (RECTANGLE_OVERLAP_LOGGING) {
                        ofstream f(LOGFILE,ios::app);
                        f<<"mergeLeft on constraint: "<<*c<<"\n";
                }
                r->deleteMinInConstraint();
                Block *l = c->left->block;              
                if (l->in.empty()) 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();
        }               
        if (RECTANGLE_OVERLAP_LOGGING) {
                ofstream f(LOGFILE,ios::app);
                f<<"merged "<<*r<<"\n";
        }
}       
void Blocks::mergeRight(Block *l) {     
        if (RECTANGLE_OVERLAP_LOGGING) {
                ofstream f(LOGFILE,ios::app);
                f<<"mergeRight called on "<<*l<<"\n";
        }
        l->setUpOutConstraints();
        Constraint *c = l->findMinOutConstraint();
        while (c != nullptr && c->slack()<0) {          
                if (RECTANGLE_OVERLAP_LOGGING) {
                        ofstream f(LOGFILE,ios::app);
                        f<<"mergeRight on constraint: "<<*c<<"\n";
                }
                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();
        }       
        if (RECTANGLE_OVERLAP_LOGGING) {
                ofstream f(LOGFILE,ios::app);
                f<<"merged "<<*l<<"\n";
        }
}
void Blocks::removeBlock(Block *doomed) {
        doomed->deleted=true;
        //erase(doomed);
}
void Blocks::cleanup() {
        for (auto i = begin(); i != end();) {
                Block *b=*i;
                if(b->deleted) {
                        i = erase(i);
                        delete b;
                } else {
                        ++i;
                }
        }
}
void Blocks::split(Block *b, Block *&l, Block *&r, Constraint *c) {
        b->split(l,r,c);
        if (RECTANGLE_OVERLAP_LOGGING) {
                ofstream f(LOGFILE,ios::app);
                f<<"Split left: "<<*l<<"\n";
                f<<"Split right: "<<*r<<"\n";
        }
        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);
}
double Blocks::cost() {
        double c = 0;
        for (Block *b : *this) {
                c += b->cost();
        }
        return c;
}