#include <vector>
#include <queue>
#include <string>
#include <cmath>
#include <sstream>

#include "Placer.h"
#include "Circuit.h"
#include "Rule.h"
#include "Piece.h"
#include "Connection.h"

//nastavenie konstant pre vykreslovanie prvkov
#define D 10
#define T 40
#define C 80
#define GRID 10
#define PIECE_SPC 60 

Placer::Placer(Circuit* circuit) {
    this->circuit = circuit;
    processQueue = new queue<Rule*>();
    waitQueue = new queue<Rule*>();
	wireNum = 0;
}

Placer::~Placer() {

}

Circuit* Placer::getCircuit() {
    return this->circuit;
}

//zisti, ci je mozne ulozit prvok, to znamena, ze vsetky pravidla, ktore reprezentuju jeho vstup su uz umiestnene
bool Placer::connect(Rule* rule) {
    Rule* tmpRule;
    for (unsigned int i = 0; i < rule->getInputs()->size(); i++) {
        tmpRule = rule->getInputs()->at(i);
        if (!circuit->isPieceIncluded(tmpRule->getName()) &&
                !circuit->isInputIncluded(tmpRule->getName())) {
            return false;
        }
    }
    return true;
}

void Placer::place(Rule* rule) {
    Piece* piece = new Piece(rule);
    Piece* tmpPiece;
    int xmax = 0;
    int ymax = 0;
    //najdenie maximalnej horizontalnej polohy vstupneho prvku
    for (unsigned int i = 0; i < rule->getInputs()->size(); i++) {
        tmpPiece = circuit->getPiece(rule->getInputs()->at(i));
        if (tmpPiece->x + tmpPiece->width > xmax){
            xmax = tmpPiece->x + tmpPiece->width;
        }
    }
    //najdenie maximalnej vertikalnej polohy okolitych prvkov, ktore su na
    //rovnakej pozicii ako ukladany prvok tz. ze ich x suradnica je rovnaka
    for (unsigned int i = 0; i < circuit->getPieces()->size(); i++) {
        tmpPiece = circuit->getPieces()->at(i);
        if (tmpPiece->x == xmax && tmpPiece->y + tmpPiece->height > ymax) {
            ymax = tmpPiece->y + tmpPiece->height;
        }
    }
    piece->x = xmax + PIECE_SPC;
    piece->y = ymax + PIECE_SPC;
    //cout << "Adding piece for rule " << rule->getName() << endl;
    circuit->addPiece(piece);
}

//prvotne umiestnenie prvkov podla moznosti ulozenia. Uklada postupne od vstupov k vystupom
void Placer::primalPlace() {
    unsigned int i;
    Rule* rule;
    bool connectOK;
    //naplnenie fronty ete neumiestnenych prvkov
    for (i = 0; i < circuit->getRules()->size(); i++) {
        processQueue->push(circuit->getRules()->at(i));
    }
    do {
        connectOK = false; 
        while (processQueue->size() > 0) {
            rule = processQueue->front();
            processQueue->pop();
			//test, ci je mozne umiestnit prvok
            if (!connect(rule)) {
                //cout << "Adding to waitQueue rule " << rule->getName() << endl; 
				//ak sa prvok neda umiestnit, ulozi sa to vyckavacej fronty
                waitQueue->push(rule);
            }else {
                connectOK = true;
                place(rule);
            }
        }
        while (waitQueue->size() > 0) {            
            //cout << "Getting from waitQueue rule " << waitQueue->front()->getName() << endl;
            processQueue->push(waitQueue->front());
            waitQueue->pop();
        }

    } while (processQueue->size() > 0 && connectOK);
	//presunutie vystupov na koniec
	int outputXMax=0;
	Piece* po;
	for(unsigned int i = 0; i < circuit->getOutputs()->size(); i++){
		po = circuit->getPiece(circuit->getOutputs()->at(i)->getName());
		if(outputXMax < po->x){
			outputXMax = po->x;
		}
	}
	for(unsigned int i = 0; i < circuit->getOutputs()->size(); i++){
		po = circuit->getPiece(circuit->getOutputs()->at(i)->getName());
		po->x = outputXMax;
	}
}

void Placer::mapLayerHoriz(){
	Piece *pk;
	Piece *p;
	vector<int> *usedPx = new vector<int>();
	vector<Piece*> *pieces = circuit->getPieces();
	vector<Piece*> *mapLayer;

	mapLayers= new vector<vector<Piece*>*>();

	do{
		pk=NULL;
		//Vyber najmensieho nepouziteho p.x
		for(unsigned int j = 0; j < pieces->size(); j++){
			p = pieces->at(j);
			if(pk == NULL){
				if(find(usedPx->begin(), usedPx->end(), p->x) == usedPx->end()){
					pk = p;
				}
			}
			else if(pk->x > p->x && find(usedPx->begin(), usedPx->end(), p->x) == usedPx->end()){
				pk = p;
			}
		}
		//vytvorenie mapy podla pk.x
		if(pk != NULL){
			usedPx->push_back(pk->x);
			mapLayer = new vector<Piece*>();
			for(unsigned int i = 0; i < pieces->size(); i++){
				p = pieces->at(i);
				if(p->x == pk->x){
					mapLayer->push_back(p);
				}
			}
			mapLayers->push_back(mapLayer);
		}
	}while(pk != NULL);
}

void Placer::mapDensity(){
	vector<Piece*>* mapLayer;

	densityMap = new vector<int>();

	for(unsigned int i = 0; i < mapLayers->size(); i++){
		mapLayer = mapLayers->at(i);
		densityMap->push_back(mapLayer->size());
	}
}

bool Placer::moveCandidate(int levelFrom){
	vector<Piece*>* mapLayer;
	vector<Piece*>* mapLayerInc;
	Piece* pc;
	Piece* p;
	Rule* r;
	bool candidateOk;
	mapLayer = mapLayers->at(levelFrom);
	mapLayerInc = mapLayers->at(levelFrom + 1);

	int newX = mapLayerInc->at(0)->x;

	for(unsigned int ipc = 0; ipc < mapLayer->size(); ipc++){
		pc = mapLayer->at(ipc);
		candidateOk = true;
		for(unsigned int ip = 0; ip < mapLayerInc->size(); ip++){
			p = mapLayerInc->at(ip);
			for(unsigned int ir = 0; ir < p->rule->getInputs()->size(); ir++){
				r = p->rule->getInput(ir);
				//cout << "testing rule input " << r->getName() << " with piece " << pc->rule->getName() << endl;
				if(circuit->getPiece(r) == pc){
					candidateOk=false;
				}
			}
		}
		if(candidateOk){
			//cout << "moving candidate " + pc->rule->getName() << endl;
			mapLayer->at(ipc) = NULL;
			mapLayer->erase(mapLayer->begin() + ipc);
			mapLayerInc->push_back(pc);
			pc->x = newX;
			return true;
		}
	}
	return false;
}

void Placer::horizontalPieceOptm(){
	bool change=true;
	int d1,d2;

    mapLayerHoriz();
	while(change){
		mapDensity();
		change = false;
		for(unsigned int i = 0; i < densityMap->size() - 1; i++){
			d1 = densityMap->at(i);
			d2 = densityMap->at(i + 1);
			if( d1 > d2 && d1 > d2 + 1){
				change |= moveCandidate(i);
			}
		}
	}

	//Tu by mali byt prvky pekne usporiadane
}

void Placer::verticalPieceOptm(){
	vector<Piece*>* mapLayer;
	vector<Piece*>* map=new vector<Piece*>();
	Piece* p;
	for(unsigned int ims = 0; ims < mapLayers->size(); ims++){
		map=new vector<Piece*>();
		mapLayer = mapLayers->at(ims);
		yoptm = new vector<int>();
		for(unsigned int ip = 0; ip < mapLayer->size(); ip++){
			p = mapLayer->at(ip);
			calculateYOptm(p);
			moveToYOptm(p, map);
		}
		mapLayer->insert(mapLayer->begin(), map->begin(), map->end());
		delete(map);
		delete(yoptm);
	}
}

void Placer::calculateYOptm(Piece *p){
	Rule* rInput;
	yoptm->clear();
	for(unsigned int i = 0; i < p->rule->getInputs()->size(); i++){
		rInput = p->rule->getInput(i);
		yoptm->push_back(circuit->getPiece(rInput)->y - p->inputY->at(0));
	}
}

void Placer::moveToYOptm(Piece *p, vector<Piece*>* m){
	Piece* p1;
	Piece* p2;
	vector<Piece*> map = *m;
	bool moved = false;
	int y;

	sort(map.begin(), map.end());
	for(unsigned int iy = 0; (iy < yoptm->size()) && !moved; iy++){
		y = yoptm->at(iy);
		if(map.size() >= 2){
			for(unsigned int ip = 0; ip < map.size()-1; ip++){
				p1 = map.at(ip);
				p2 = map.at(ip + 1);
				if(y < p2->y && y > p1->y + p1->height + PIECE_SPC &&
					y + p->height + PIECE_SPC < p2 ->y && 
					y + p->height + PIECE_SPC > p1->y + p1->height + PIECE_SPC){
					p->y = y;
					moved = true;
				}
			}
		}else if(map.size() == 1){
			p1 = map.at(0);
			if((y > p1->y + p1->height + PIECE_SPC && 
				y + p->height + PIECE_SPC >  p1->y + p1->height + PIECE_SPC) || 
				y + p->height + PIECE_SPC < p1->y){
				p->y = y;
				moved = true;
			}
		}else{
			p->y = y;
			moved = true;
		}
	}
	if(!moved && map.size() > 0){
		p1 = *(map.begin());
		for(unsigned int ip = 0; ip < map.size(); ip++){
			p2 = map.at(ip);
			if(p1->y < p2->y){
				p1 = p2;
			}
		}
		p->y = p1->y + p1->height + PIECE_SPC;
	}
	map.push_back(p);
	vector<Piece*>* mm = &map;
	m->clear();
	m->insert(m->begin() , mm->begin(), mm->end());
}

void Placer::createNodes(){
	Piece* p;
	Node* n;
	for(unsigned int ip = 0; ip < circuit->getPieces()->size(); ip++){
		p = circuit->getPieces()->at(ip);
		for(unsigned int ir = 0; ir < p->rule->getInputs()->size(); ir++){
			n = new Node(p->x, p->y + p->inputY->at(ir), 1, 1, 0, 1);
			n->right = p->rule->getName();
			n->rightPiece = true;
			circuit->nodes.push_back(n);
		}
		n = new Node( p->x + p->width, p->y + p->outputY->at(0), 1, 1, 1, 0);
		n->left = p->rule->getName(); 
		if(p->rule->getType().compare("INPUT") == 0){
			n->x = p->x + p->width;
			n->y = p->y + p->outputY->at(0);
		}
		n->left= p->rule->getName();
		circuit->nodes.push_back(n);
	}
}

void Placer::route(){
	Rule* rStart; //pravidlo, na ktoreho vystupe bude pociatocny uzol
	Rule* rEnd; // previdlo, ne ktoreho vstup bude reprezentovat koncovy uzol
	//nStart a nEnd su pociatocny a koncovy uzol pre routovany spoj
	//nTemp je pomocny uzol pre vyhladanie pociatocneho uzlu spoju
	//ak sa nepodarilo najst nStart, tak za uzlom nTemp vytvorime novy (nTempRight)
	//tento uzol bude potom reprezentovat aj pociatocny spoj
	Node *nStart, *nEnd, *nTemp, *nTempRight = NULL;
	//int ntx, nex;
	//body cety novovytvoreneho spoju
	Point *p1, *p2;
	Connection *c, *cOriginal, *cTemp;
	stringstream ss;
	vector<Node*> Q;
	//vypocitane suradnice noveho bodu v ktorom sa bude rodelovat spojenie
	int newX, newY;
	bool startNotFound = true;
	for(unsigned int ir = 0; ir < circuit->getRules()->size(); ir++){
		//vyberieme postupne vsetky pravidla, ku korim chceme vytcorit spojenia
		rEnd = circuit->getRules()->at(ir);
		for(unsigned int iri = 0; iri < rEnd->getInputs()->size(); iri++){
			//skusime najst pravidla, na ktore sa maju naviazat na rEnd
			rStart = rEnd->getInputs()->at(iri);
			cout << "Routing from " << rStart->getName() << " to " << rEnd->getName() << endl;
			//najdenie pociatocnych a koncovych uzlov
			startNotFound = true; // zatial sa nam nepodarilo najst pociatocne pravidlo (start Not Found)
			nStart = NULL;
			nEnd = NULL;
			for(unsigned int in = 0; in < circuit->nodes.size(); in++){
				nTemp = circuit->nodes.at(in); 
				// najdeme pociatocny uzol na cestu, alebo uzol, za ktory mozeme pridat dalsi
				if(nStart == NULL && nTemp->left.compare(rStart->getName()) == 0){ // pokial uzol je zlava naviazany na pravidlo, ktore je rStart, pokuzime sa najst najblizsi uzol k tomuto pravidlu, ktory je volnu a je mozne z neho nadviazat spoj k pravidlu rEnd
					Q.clear();
					Q.push_back(nTemp); // ako prvy budeme testovat uzol hned za prvkom
					while(!Q.empty() && startNotFound){ // pokial je co testovat alebo sme nenasli pociatocny uzol
						nTemp = *Q.begin(); // budeme testovat prvok na zaciatku fronty
						Q.at(0) = NULL;
						Q.erase(Q.begin()); // tento prvok uz testovat nebudeme
						if(nTemp->freeDir()){ // ak je mozne z uzlu nadviazat, budeme ho povazovat za pociatocny
							nStart = nTemp;
							startNotFound = false;
							break; // ukoncime hladanie
						}
						if(!nTemp->rightPiece){ // zistime, ci najdeny prvok nieje na konci hladaneho spojenia, tz. uzol nieje na vstupe konecneho prvku
							nTempRight = nTemp; 
						}
						for(unsigned int icc = 0; icc < circuit->connections.size(); icc++){ // vlozime do fronty na testovanie vsetky uzly z Adj(nTemp)
							c = &(circuit->connections.at(icc));
							if(c->start == nTemp && !c->end->rightPiece){
								Q.push_back(c->end);
							}
						}
					}
				}
				// najdeme uzol, ktory je na vstupe prvku reprezentujuceho koncove pravidlo a nieje obsadeny
				if(nEnd == NULL && nTemp->right.compare(rEnd->getName()) == 0 &&
					nTemp->left.compare("") == 0){
					nEnd = nTemp;
				}
			}
			//nenasli sme ziaden vyhovujuci pociatocny uzol. Budeme si musiet preto vytvorit 
			//novy, ktory bude ihned na poslednym vyhovujucim ale obsadenym uzlom
			if(startNotFound){
				nTemp = nTempRight; // nTempRight je najpravejsi uzol spojenia, ktory nieje rightPiece, tz. ze nieje uzlom repezentujucim vstup do prvku
				//cout << "Creating new node" << endl;				
				for(unsigned int ic = 0; ic < circuit->connections.size(); ic++){ //najdeme spojnie z nami pozadovaneho prvku, ktory reprezentuje zaciatok spojenia, ktore hladame
					cTemp = &(circuit->connections.at(ic));
					if (cTemp->start->comp(nTemp) && cTemp->path.at(0).dir == Node::DIR_RIGHT){
						cOriginal = &(circuit->connections.at(ic));
					}
				}
				ss.str("");
				ss << "Wire" << wireNum; //vytvorenie mena pre nove spojenie
				wireNum++;
				newX = nTemp->x + 10;
				newY = nTemp->y;
				while(circuit->isThereConnection(newX, newY, cOriginal->name)){
					newX += 10;
				}
				nTempRight = new Node(newX, newY, 0, 0, 1, 1); // vytvorime si uzol ihned za najpravejsim nevstupovym uzlom
				//TODO otestovat, ci sa tam nenachadza nejaky spoj, okrem toho, na ktorom to vytvarame (kolme krizenie)
				c = new Connection(); // vytvorime si nove spojenie
				c->name = ss.str();
				//cout << ss.str() << endl;
				nTempRight->left = c->name; // najpravejsi uzol sa bude vlavo pripojeny na nove spojenie
				cOriginal->start->right = c->name; // pociatocny bod existujuceho spojenia sa v pravo pripoji na novo vytvoreny spoj
				nTempRight->right = cOriginal->name; // novy uzol sa na spoj pripoji lava
				cOriginal->start = nTempRight; // predosle spojenie bude zacinat od noveho uzlu
				//ntx = circuit->iOfNode(nTemp); // index najpravejsieho uzlu
				//nex = circuit->iOfNode(nEnd); // index posledneho uzlu v mnozine uzlov obvodu
				circuit->nodes.push_back(nTempRight);
				//nTemp = circuit->nodes.at(ntx);
				//nEnd = circuit->nodes.at(nex);
				p1 = new Point();
				p1->x = nTemp->x;
				p1->y = nTemp->y;
				p2 = new Point();
				p2->x = nTempRight->x;
				p2->y = nTempRight->y;
				//cout << "From " << p1->x << "," << p1->y << " to " 
				//	<< p2->x << ","<< p2->y << endl; 
				c->start = nTemp;
				c->end = nTempRight; // nove spojenie pojde od najpravejsieho uzlu az po novy uzol
				c->inner = true;
				c->path.push_back(*p1);
				c->path.push_back(*p2); // bude obsahovat len dva klucove body (zaciatku a konca)
				cOriginal->path.at(0) = *p2;
				nStart = nTempRight;
				circuit->connections.push_back(*(c)); // do mnoziny spojeni obvodu pridamenovo vytvorene spojenie
			}
			//routovanie cesty z nStart do nEnd
			//cout << "Connection " << nStart.rin->getName() << " to " << nEnd.rout->getName() << endl;
			//cout << "[" << nStart.x << "," << nStart.y << "] to " << 
			//	"[" << nEnd.x << "," << nEnd.y << "]" << endl;
			routeConnection(nStart, nEnd); // spojenie od ovlneho pociatocneho uzlu az po ten konecny naroutujeme
		}
	}
}

// funkcia ohodnocujuca cestu
double Placer::f(vector<Point> *path, Node *nEnd){
	double g,h;
	int t = 0, c = 0;
	Point pFirst,pLast;
	pFirst = *(path->begin());
	pLast = *(path->end() - 1);
	h = double(abs(nEnd->x - pLast.x) + abs(nEnd->y - pLast.y));
//	cout << "Path : ";
	//cout << "[" << path->at(0).x << "," << path->at(0).y << "],";
	for(unsigned int i = 0; i < path->size()-1; i++){
	//	cout << "[" << path->at(i+1).x << "," << path->at(i+1).y << "],";
		if(path->at(i).dir != path->at(i+1).dir){
			t++;
		}
		//c += circuit->numOfPaths(path->at(i), path->at(i+1));
	}
	g = path->size() * D + t * T; //+c * C;
	//cout << "\t" << h;
	return g + h;
}

void Placer::routeConnection(Node *nStart, Node *nEnd){
	//najdeme cestu medzi dvomi uzlami za pouzitia A* algoritmu
	vector<Point> path, *pth, *ppth;
	vector<Point> closed;
	vector<vector<Point>*> Q; // fronta buducich ciest
	Connection *c;
	stringstream ss;
	Node *nTemp;
	int pPos; // premenna udavajuca poziciu cesty vo fronte. Pouziva sa najma pri odstraneni cesty z fronty
	Point* p = new Point(); // pociatocny bod cesty
	Point* pp, *ppTmp;
	p->x = nStart->x;
	p->y = nStart->y;
	p->dir = Node::DIR_RIGHT;
	path.push_back(*p); // pociatcna cesta path{p}
	Q.push_back(&path); // pridame ju do fronty a spustime algoritmus
	while(!Q.empty()){ // pokial mame este nejake cesty na preskumanie
		pth = NULL; // cesta, ktoru budeme skumat
		pPos = -1; // jej pozicia v Q
		for(unsigned int ip = 0; ip < Q.size(); ip++){ // pre vsetky cest z Q
			ppth = Q.at(ip);
			if(pth == NULL){ // pokial sme este ziadnu cestu nevybrali bude pth prva cesta
				pth = ppth;
				pPos = ip;
			}
			else if(f(pth, nEnd) > f(ppth, nEnd)){ // ak sme uz cestu vybrali, zistime, ci nahodou nieje nova cesta vyhodnejsia,tz. ci nema nizsiu hodnotu f(x)
				//cout << "checking f=" << f(pth, nEnd) << endl;
				pth = ppth;
				pPos = ip;
			}
		}
		//cout << "going with [" << (*(pth->end() - 1)).x << "," << (*(pth->end() - 1)).y << "] f=" << f(pth, nEnd) << "||" << nEnd.x - (*(pth->end() - 1)).x << "," << nEnd.y - (*(pth->end() - 1)).y << "=" << abs(nEnd.x - (*(pth->end() - 1)).x)+abs(nEnd.y - (*(pth->end() - 1)).y) << endl;
		Q.at(pPos) = NULL;
		Q.erase(Q.begin() + pPos); // odstranime castu, ktoru sme si vybrali na preskumanie
		//cout << "checking [" << (*(pth->end() - 1)).x << "," << (*(pth->end() - 1)).y << "]" << endl;
		closed.push_back(*(pth->end() - 1)); // posledny uzol cesty uzavrieme, aby sme sa uz k nemu nevracali
		if((*(pth->end() - 1)).x == nEnd->x && (*(pth->end() - 1)).y == nEnd->y){ // ak sa posledny uzol cesty zhoduje s poslednym uzlom routovaneho spojenia, tuto cestu oznacime za spoj a upravime parametre koncoveho a pociatocneho bodu
			ss.str("");
			ss << "Wire" << wireNum;
			wireNum++;
			c = new Connection();
			c->name = ss.str();
			if(pth->at(0).dir == Node::DIR_LEFT){
				nStart->left = c->name;
			}
			if(pth->at(0).dir == Node::DIR_RIGHT){
				nStart->right = c->name;
			}
			if(pth->at(0).dir == Node::DIR_UP){
				nStart->up = c->name;
			}
			if(pth->at(0).dir == Node::DIR_DOWN){
				nStart->down = c->name;
			}
			nEnd->left = c->name;
			nStart->dir[pth->at(0).dir] = 1;
			nEnd->dir[Node::DIR_LEFT] = 1;
			c->start = nStart;
			c->end = nEnd;
			c->path = *pth;
			//zoptimalizujeme najdenu cestu pomocou metody mergePoints
			mergePoints(c);
			circuit->connections.push_back(*c); // spoj ulozime do mnoziny spojov obvodu
			//cout << "For node " << nStart.x << "," << nStart.y << " disable " << c->path.at(0).dir << endl;
			//TODO odstranit a obsadit spojenie na nStart
			// obsadime spoj z ktoreho sme nasli spojenie
			for(unsigned int in = 0; in < circuit->nodes.size(); in++){
				nTemp = circuit->nodes.at(in);
				if(nTemp->comp(nStart)){
					nTemp->dir[c->path.at(0).dir] = 1;
					// zapiseme do daneho smeru najdenu cestu
					switch(c->path.at(0).dir){
						case Node::DIR_LEFT:
							nTemp->left = c->name;
							break;
						case Node::DIR_RIGHT:
							nTemp->right = c->name;
							break;
						case Node::DIR_UP:
							nTemp->up = c->name;
							break;
						case Node::DIR_DOWN:
							nTemp->down = c->name;
							break;
					}
				}
			}
			//ukoncime metodu
			return;
		}
		p = &(*(pth->end() - 1)); //p je posledny uzol cesty
		//ak sme na zaciatku a mozeme sa hybat do nejakeho smeru, akebo sme niekde v strede tak novy bod, ktory nieje v mnozine Closed alebo nekoliduje so ziadnym prvkom / spojom, zaradime a vytvorime tym novu castu, ktoru ulozime do Q
		//Tento postuo robime pre vsetky 4 smery, ktore mozu viest z jedneho uzlu
		if((p->x == nStart->x && p->y == nStart->y && nStart->dir[Node::DIR_RIGHT] == 0) || 
			(p->x != nStart->x || p->y != nStart->y )){
			ppth = new vector<Point>();
			pp = new Point();
			ppTmp = &(*(pth->end() - 1));
			pp->x = ppTmp->x + GRID;
			pp->y = ppTmp->y;
			pp->dir = Node::DIR_RIGHT;
			if(!circuit->isTherePiece(pp, nEnd) && find(closed.begin(), closed.end(), pp)==closed.end() 
				&& pp->x >=0 && pp->y >= 0 && !circuit->arePntsOnTheSamePath(pp, ppTmp)){
				ppth->insert(ppth->begin(),pth->begin(),pth->end());
				ppth->push_back(*pp);
				Q.push_back(ppth);
			}
		}
		if((p->x == nStart->x && p->y == nStart->y && nStart->dir[Node::DIR_LEFT] == 0) || 
			(p->x != nStart->x || p->y != nStart->y )){
			ppth = new vector<Point>();
			pp = new Point();
			ppTmp = &(*(pth->end() - 1));
			pp->x = ppTmp->x - GRID;
			pp->y = ppTmp->y;
			pp->dir = Node::DIR_LEFT;
			if(!circuit->isTherePiece(pp, nEnd) && find(closed.begin(), closed.end(), pp)==closed.end() 
				&& pp->x >=0 && pp->y >= 0 && !circuit->arePntsOnTheSamePath(pp, ppTmp)){
				ppth->insert(ppth->begin(),pth->begin(),pth->end());
				ppth->push_back(*pp);
				Q.push_back(ppth);
			}
		}
		if((p->x == nStart->x && p->y == nStart->y && nStart->dir[Node::DIR_DOWN] == 0) || 
			(p->x != nStart->x || p->y != nStart->y )){
			ppth = new vector<Point>();
			ppTmp = &(*(pth->end() - 1));
			pp = new Point();
			pp->x = ppTmp->x;
			pp->y = ppTmp->y + GRID;
			pp->dir = Node::DIR_DOWN;
			if(!circuit->isTherePiece(pp, nEnd) && find(closed.begin(), closed.end(), pp)==closed.end() 
				&& pp->x >=0 && pp->y >= 0 && !circuit->arePntsOnTheSamePath(pp, ppTmp)){
				ppth->insert(ppth->begin(),pth->begin(),pth->end());
				ppth->push_back(*pp);
				Q.push_back(ppth);
			}
		}
		if((p->x == nStart->x && p->y == nStart->y && nStart->dir[Node::DIR_UP] == 0) || 
			(p->x != nStart->x || p->y != nStart->y )){
			ppth = new vector<Point>();
			ppTmp = &(*(pth->end() - 1));
			pp = new Point();
			pp->x = ppTmp->x;
			pp->y = ppTmp->y - GRID;
			pp->dir = Node::DIR_UP;
			if(!circuit->isTherePiece(pp, nEnd) && find(closed.begin(), closed.end(), pp)==closed.end() 
				&& pp->x >=0 && pp->y >= 0 && !circuit->arePntsOnTheSamePath(pp, ppTmp)){
				ppth->insert(ppth->begin(),pth->begin(),pth->end());
				ppth->push_back(*pp);
				Q.push_back(ppth);
			}
		}
	}
}

void Placer::mergePoints(Connection *c){
	Point *p1,*p2;
	unsigned int ip = 1;
	while(ip < c->path.size() - 2){
		p1 = &(c->path.at(ip));
		p2 = &(c->path.at(ip+1));
		if(p1->dir == p2->dir){
			p1->x = p2->x;
			p1->y = p2->y;
			c->path.erase(c->path.begin() + ip + 1);
		}
		else{
			ip++;
		}
	}
}

void Placer::placeCircuit() {
    primalPlace();
    horizontalPieceOptm();
    verticalPieceOptm();
	createNodes();
	route();
}

