#include <map>

#include <list>

#include <libvpsc/remove_rectangle_overlap.h>

#include "cola.h"

using namespace std;

namespace cola {

Component::~Component() {

for(unsigned i=0;i<scx.size();i++) {

delete scx[i];

}

for(unsigned i=0;i<scy.size();i++) {

delete scy[i];

}

}

void Component::moveRectangles(double x, double y) {

for(unsigned i=0;i<rects.size();i++) {

rects[i]->moveCentreX(rects[i]->getCentreX()+x);

rects[i]->moveCentreY(rects[i]->getCentreY()+y);

}

}

Rectangle* Component::getBoundingBox() {

double llx=DBL_MAX, lly=DBL_MAX, urx=-DBL_MAX, ury=-DBL_MAX;

for(unsigned i=0;i<rects.size();i++) {

llx=min(llx,rects[i]->getMinX());

lly=min(lly,rects[i]->getMinY());

urx=max(urx,rects[i]->getMaxX());

ury=max(ury,rects[i]->getMaxY());

}

return new Rectangle(llx,urx,lly,ury);

}

namespace ccomponents {

struct Node {

unsigned id;

bool visited;

vector<Node*> neighbours;

list<Node*>::iterator listPos;

Rectangle* r;

};

// Depth first search traversal of graph to find connected component

void dfs(Node* v,

list<Node*>& remaining,

Component* component,

map<unsigned,pair<Component*,unsigned> > &cmap) {

v->visited=true;

remaining.erase(v->listPos);

cmap[v->id]=make_pair(component,component->node_ids.size());

component->node_ids.push_back(v->id);

component->rects.push_back(v->r);

for(unsigned i=0;i<v->neighbours.size();i++) {

Node* u=v->neighbours[i];

if(!u->visited) {

dfs(u,remaining,component,cmap);

}

}

}

}

using namespace ccomponents;

// for a graph of n nodes, return connected components

void connectedComponents(

const vector<Rectangle*> &rs,

const vector<Edge> &es,

const SimpleConstraints &scx,

const SimpleConstraints &scy,

vector<Component*> &components) {

unsigned n=rs.size();

vector<Node> vs(n);

list<Node*> remaining;

for(unsigned i=0;i<n;i++) {

vs[i].id=i;

vs[i].visited=false;

vs[i].r=rs[i];

vs[i].listPos = remaining.insert(remaining.end(),&vs[i]);

}

vector<Edge>::const_iterator ei;

SimpleConstraints::const_iterator ci;

for(ei=es.begin();ei!=es.end();ei++) {

vs[ei->first].neighbours.push_back(&vs[ei->second]);

vs[ei->second].neighbours.push_back(&vs[ei->first]);

}

map<unsigned,pair<Component*,unsigned> > cmap;

while(!remaining.empty()) {

Component* component=new Component;

Node* v=*remaining.begin();

dfs(v,remaining,component,cmap);

components.push_back(component);

}

for(ei=es.begin();ei!=es.end();ei++) {

pair<Component*,unsigned> u=cmap[ei->first],

v=cmap[ei->second];

assert(u.first==v.first);

u.first->edges.push_back(make_pair(u.second,v.second));

}

for(ci=scx.begin();ci!=scx.end();ci++) {

SimpleConstraint *c=*ci;

pair<Component*,unsigned> u=cmap[c->left],

v=cmap[c->right];

assert(u.first==v.first);

u.first->scx.push_back(

new SimpleConstraint(u.second,v.second,c->gap));

}

for(ci=scy.begin();ci!=scy.end();ci++) {

SimpleConstraint *c=*ci;

pair<Component*,unsigned> u=cmap[c->left],

v=cmap[c->right];

assert(u.first==v.first);

u.first->scy.push_back(

new SimpleConstraint(u.second,v.second,c->gap));

}

}

void separateComponents(const vector<Component*> &components) {

unsigned n=components.size();

Rectangle* bbs[n];

double origX[n], origY[n];

for(unsigned i=0;i<n;i++) {

bbs[i]=components[i]->getBoundingBox();

origX[i]=bbs[i]->getCentreX();

origY[i]=bbs[i]->getCentreY();

}

removeRectangleOverlap(n,bbs,0,0);

for(unsigned i=0;i<n;i++) {

components[i]->moveRectangles(

bbs[i]->getCentreX()-origX[i],

bbs[i]->getCentreY()-origY[i]);

delete bbs[i];

}

}

}