// graph.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "graph.h"
#include "stdio.h"
#include "stdlib.h"
#include "memory.h"

#pragma warning(disable : 4311)
#pragma warning(disable : 4312)
#pragma warning(disable : 4996)


#define PSSIZEX 565
#define PSSIZEY 842
// -----------------------------------------------------------------
// funkce zjisti, zdali se dve usecky zadane dvema body krizi
bool Crossing(POINT a1, POINT a2, POINT b1, POINT b2){	
	float ax1, ax2, bx1,bx2;
	if ((a2.y<b1.y) || (a1.y>b2.y)) return false;
	if(a1.y==b1.y){
		ax1=(float)(a1.x);
		bx1=(float)(b1.x);
	}
	else if (a1.y<b1.y){
		//zkratime zacatek prni ucecky
		ax1=((float)(b1.y-a1.y)*(a2.x-a1.x))/((float)(a2.y-a1.y))+a1.x;
		bx1=(float)b1.x;
	}
	else {
		//zkratime zacatek druhe usecky
		ax1=(float)a1.x;
		bx1=((float)(a1.y-b1.y)*(b2.x-b1.x))/((float)(b2.y-b1.y))+b1.x;	
	}

	if(a2.y==b2.y){
		ax2=(float)(a2.x);
		bx2=(float)(b2.x);
	}
	else if(a2.y<b2.y){
		//zkratime konec druhe usecky
		bx2=((float)(a2.y-b1.y)*(b2.x-b1.x))/((float)(b2.y-b1.y))+b1.x;	
		ax2=(float)a2.x;
	}
	else {
		//zkratime konec prvni ucecky
		ax2=((float)(b2.y-a1.y)*(a2.x-a1.x))/((float)(a2.y-a1.y))+a1.x;
		bx2=(float)b2.x;
	}
	if(ax1>bx1){
		if(ax2>=bx2) return false;
		else return true;
	}
	else{
		if(ax2<=bx2) return false;
		else return true;
	}
}

// -----------------------------------------------------------------
//	Inicializuje zakladni promene, vytvori koncovy uzel one 
//	a vytvori prazdne pole grafu o velikosti X a Y
bool InitGraph(GRAPH *g, GRAPHINFO *info, unsigned int x, unsigned int y){
	g->inserted=NULL;
	g->size.x=x;
	g->size.y=y;
	g->shift.x=0;
	g->shift.y=0;
	g->graph=(PNODE **)malloc(x*sizeof(PNODE));
	if(g->graph==NULL){
		fprintf(stderr,"Can't allocate memory\n");
		return false;
	}
	for(int i=0; i<g->size.x; i++){
		g->graph[i] = (PNODE *)malloc(y*sizeof(PNODE));
		memset(g->graph[i], 0, y*sizeof(PNODE));
		if(g->graph[i]==NULL){
			fprintf(stderr,"Can't allocate memory\n");
			return false;
		}
	}

	g->one = (PNODE) malloc(sizeof(NODE));
	g->one->pThen=NULL;
	g->one->pElse=NULL;
	g->one->type=1;
	g->one->loc.x=0;
	g->one->loc.y=y-1;
	g->graph[0][y-1]=g->one;
	g->one->name=(char *)malloc(2*sizeof(char));
	if(g->one->name==NULL){
		fprintf(stderr,"Can't allocate memory\n");
		return false;
	}
	strcpy(g->one->name, "1");

	return true;
}

// -----------------------------------------------------------
//	Prepocita souradnice uzlu v grafu na souradnice v bodech 
//	pozitych pro vykresleni grafu
POINT GetCoord(GRAPH *g, POINT A){
	POINT ret;
	ret.x=(A.x-g->shift.x)*g->grid+(g->grid/2);
	ret.y=(A.y-g->shift.y+1)*g->grid+(g->grid/2);
	return ret;
}

// -----------------------------------------------------------------
//	Vrati rozmery ctverce, jenz se vykresluje jako uzel
void GetNameRect(GRAPH *g, POINT witch, POINT *retA, POINT *retB){
	POINT clientSize;
	clientSize.x=0;
	clientSize.y=16;
	*retA=GetCoord(g, witch);
	if(g->graph[witch.x][witch.y]->type>1){
		*retB = *retA;
		return;
	}
	if(witch.x==g->one->loc.x && witch.y==g->one->loc.y){
		clientSize.x=10;
	}
	
	else if(g->graph[witch.x][witch.y]->name!=NULL){
		clientSize.x=11*(int)strlen(g->graph[witch.x][witch.y]->name);
	}
	retA->x-=(clientSize.x+g->border)/2;
	retA->y-=(clientSize.y+g->border)/2;
	retB->x=retA->x+clientSize.x+g->border;
	retB->y=retA->y+clientSize.y+g->border;
}

// -----------------------------------------------------------------
//	Presune uzel ze souradnic [srcX][srcy] na souradnice [destX][destY]
bool MoveNode(GRAPH *g, int srcX, int srcY, int destX, int destY){
	g->graph[destX][destY]=g->graph[srcX][srcY];
	g->graph[srcX][srcY]=NULL;
	g->graph[destX][destY]->loc.x=destX;
	g->graph[destX][destY]->loc.y=destY;
	return true;
}

// -----------------------------------------------------------------
//	Vlozi mezi uzel na souradnicich [x][y] ohyby
//	naslednich techto uzlu bude child
//	comp urcuje, o jaky typ novych falesnych uzlu cary pujde 


NODE* InsertDummy(GRAPH *g,NODE *child, int x, int y, int comp){
	NODE *newNode=child, *oldNode=child;
	INSNODE *list=g->inserted;
	if(list!=NULL) while(list->next!=NULL) list=list->next;
	for(int i=child->loc.y-1;i>y;i--){
		newNode=(NODE *)malloc(sizeof(NODE));
		if(list==NULL){ 
			g->inserted=(INSNODE *)malloc(sizeof(INSNODE));
			list=g->inserted;
		}
		else {
			list->next=(INSNODE *)malloc(sizeof(INSNODE));
			list=list->next;
		}
		list->newNode=newNode;
		list->pBDNode=NULL;
		list->next=NULL;
		if(comp==4 || comp==5){
			newNode->type=4;
			newNode->comp= (comp==5)?true:false;
		}
		else if(comp>-1) {
			newNode->type=3;
			newNode->comp=comp?true:false;
		}
		else{
			newNode->type=2;
		}

		newNode->pThen=child;
		newNode->loc.x=x;
		newNode->loc.y=i;
		newNode->pElse=oldNode;
		g->graph[x][i]=newNode;
		oldNode=newNode;
	}
	return newNode;
}

// -----------------------------------------------------------------------------------
//	Tato funkce se pouziva pro nacitani grafu z BDD. Vola se rekurentne a v kazdem
//	kroku prida jeden uzel parametr f je ukazatel na uzel z BDD, jez se pridava do grafu
//	data je sdilena promena jenz udava X souradnice prvního uplně volného slouce
//	grafu. 3 parametr - name je ukazatel na pole retezecu se jmeny literalu parametr 
//	level urcuje vrstu, do niz se novy uzel prida a posledni paramter comp je -1 pokud 
//	do podgrafu vede hrana pThen, 0 pokud pElse, 1 pElse negovana, 2 pokud je to hrana z
//	korene, 3 z korene negovana


Node* LoadSubGraph(GRAPH *g, DdNode *f, int *data, char **name, int level, int comp){
	INSNODE *find;	
	char buffer[MAXNODENAME];
	NODE *pNode;
	int index=Cudd_NodeReadIndex(f)+1;
	if(Cudd_IsConstant(f)){
		return InsertDummy(g, g->one, *data, level, comp);
	}
	//prohleda seznam jiz vlozenych uzlu
	find=g->inserted;
	if(find!=NULL){
		if(find->pBDNode==Cudd_Regular(f)) {
			return InsertDummy(g, find->newNode, *data, level, comp);
		}
		while(find->next!=NULL){
			find=find->next;
			if(find->pBDNode==f) return InsertDummy(g, find->newNode, *data, level, comp);
		}
		find->next=(INSNODE *)malloc(sizeof(INSNODE));
		find=find->next;
	}
	else{
		g->inserted=(INSNODE *)malloc(sizeof(INSNODE));
		find=g->inserted;
	}
	find->next=NULL;
	find->pBDNode=Cudd_Regular(f);	
	//vytvori novy uzel
	pNode= (PNODE)malloc(sizeof(NODE));
	pNode->pElse=LoadSubGraph(g, Cudd_E(f), data, name, index, Cudd_IsComplement(Cudd_E(f)));
	(*data)++;
	find->newNode=pNode;
	if(pNode==NULL) {
		fprintf(stderr,"Can't alocate memory\n");
		Cudd_GraphDelete(g);
	}
	pNode->comp=Cudd_IsComplement(Cudd_E(f));
	pNode->type=0;
	pNode->loc.y=index;
	pNode->loc.x=*data;	
	g->graph[*data][index]=pNode;
	if(name!=NULL){
		pNode->name=(char *)malloc(sizeof(char)*strlen(name[index-1]));	
		if(pNode->name==NULL) {
			fprintf(stderr,"Can't alocate memory\n");
			Cudd_GraphDelete(g);
		}
		strcpy(pNode->name, name[index-1]);
	}
	else{
		buffer[0]='x';
		itoa(pNode->loc.y, &buffer[1], 10);
		pNode->name=(char *)malloc(sizeof(char)*strlen(buffer));
		if(pNode->name==NULL) {
			fprintf(stderr,"Can't alocate memory\n");
			Cudd_GraphDelete(g);
		}
		strcpy(pNode->name, buffer);
	}
	(*data)++;
	pNode->pThen=LoadSubGraph(g, Cudd_T(f), data, name, index, -1);
	pNode->pElse=InsertDummy(g, pNode->pElse, pNode->pElse->loc.x, pNode->loc.y, pNode->comp);
	pNode->pThen=InsertDummy(g, pNode->pThen, pNode->pThen->loc.x, pNode->loc.y, -1);

	return pNode;
}

// -----------------------------------------------------------------------------------
//	Funkce SwapNode prohodi v grafu dva uzle dane 2. a 3. parametrem

void SwapNode(GRAPH *g, PNODE frs, PNODE sec){
	POINT tmp=frs->loc;
 	g->graph[frs->loc.x][frs->loc.y]=sec;
	g->graph[sec->loc.x][sec->loc.y]=frs;
	frs->loc=sec->loc;
	sec->loc=tmp;
}

// -----------------------------------------------------------------------------------
//	Funkce Shrink premistuje uzly a vynecha vsechny mezery mezi jednotlivymi uzly

void Shrink(GRAPH *g){
	int find;
	bool free=true;
	for(int j=0;j<g->size.y;j++){
		find=-1;
		for(int i=0;i<g->size.x;i++){		
			if(find>=0){
				if(g->graph[i][j]==NULL) continue;
				MoveNode(g, i,j, find++,j);
			}
			else{
				if(g->graph[i][j]!=NULL) continue;
				find=i;
			}
		}
	}
}

// -----------------------------------------------------------------------------------
//	Tato funkce vraci, kolikrat na dane usecce urcene body A a B dojde k zasahu hrany  
//	obdelniku jenz ohranicuje text uzlu


unsigned int CrossPoint(GRAPH *g, POINT A, POINT B){
	POINT P, rectBegin, rectEnd, R, Q;
	int tmp;
	unsigned int ret=0;
	//zjisti, jestli usecka neprotina nejaky bod
	for(P.y=A.y+1;P.y<B.y;P.y++){
		P.x=long((float)((P.y-A.y)*(B.x-A.x))/(float)(B.y-A.y)+A.x);
		P.x+=(P.y-A.y)*(B.x-A.x)%(B.y-A.y)>((B.y-A.y)/2)?1:0;
		
		
		if(g->graph[P.x][P.y]!=NULL) {						
			if(g->graph[P.x][P.y]->type<=1){			
				GetNameRect(g, P, &rectBegin, &rectEnd);
				R=GetCoord(g, A);
				Q=GetCoord(g, B);
				if(Crossing(R, Q, rectBegin, rectEnd)) 
					ret++;
				else {
					tmp=rectBegin.y;
					rectBegin.y=rectEnd.y;
					rectEnd.y=tmp;
					if(Crossing(R, Q, rectBegin, rectEnd)) 
						ret++;
				}
			}
		}
	}
	return ret;
}

// --------------------------------------------------------------------------------------
//	Tato funkce "zkousi" odmazavat falesne uzly v zavislosti na vysledku hodnotici funkce
bool DelDummy(GRAPH *g){
	double oldEval, newEval;
	INSNODE *iter=g->inserted;
	INSNODE *find=NULL, *del;
	PNODE tmp,cur;
	oldEval=Cudd_GraphEvaluate(g, false);
	bool ret=false;
	while(iter!=NULL){
		if(iter->newNode->pElse->type>1 && iter->newNode->pElse!=g->one){
			find=g->inserted;
			
			tmp=iter->newNode->pElse;
			cur=iter->newNode;
			if(find->newNode!=tmp) while(find->next->newNode!=tmp) 
				find=find->next;
			del=find->next;
			find->next=del->next;
			g->graph[tmp->loc.x][tmp->loc.y]=NULL;
			cur->pElse=tmp->pElse;

			newEval=Cudd_GraphEvaluate(g, false);
			if(newEval>oldEval){
				cur->pElse=tmp;
				g->graph[tmp->loc.x][tmp->loc.y]=tmp;
				find->next=del;
			}
			else{
				oldEval=newEval;
				free(tmp);
				free(del);
				ret=true;
			}
		}
		if(!iter->newNode->type && iter->newNode->pThen!=g->one){
			if(iter->newNode->pThen->type){
				tmp=iter->newNode->pThen;
				cur=iter->newNode;
				find=g->inserted;
				if(find->newNode!=tmp) 
					while(find->next->newNode!=tmp && find!=NULL) find=find->next;
				del=find->next;
				find->next=del->next;
				g->graph[tmp->loc.x][tmp->loc.y]=NULL;
				cur->pThen=tmp->pElse;
				newEval=Cudd_GraphEvaluate(g, false);
				if(newEval>oldEval){
					cur->pThen=tmp;
					g->graph[tmp->loc.x][tmp->loc.y]=tmp;
					find->next=del;
				}
				else{
					oldEval=newEval;
					free(del);
					free(tmp);
					ret=true;
				}
			}
		}
		iter=iter->next;
	}
	return ret;
}

// ---------------------------------------------------------------------------------------------
//	Tato funkce presune uzly v poli grafu tak, aby nejlevejsi uzel v grafu zacinal na souradnici x==0.
//	Pote zmensi(dealokuje) pravu cast pole, v niz se nenachazeji zadny uzel

void FreeUnused(GRAPH *g){
	int maxX, minX;
	bool rowFree=true;
	for(minX=0;rowFree;minX++){
		for(int j=0;j<g->size.y;j++){
		if(g->graph[minX][j]!=NULL){
				rowFree=false;
				break;
			}
		}
	}
	if(--minX >0){
		for(int i=minX;i<g->size.x;i++){
			for(int j=0;j<g->size.y;j++){
				if(g->graph[i][j]!=NULL) MoveNode(g, i, j, i-minX, j);
			}
		}
	}
	rowFree=true;
	for(maxX=g->size.x-1;rowFree;maxX--){
		for(int j=0;j<g->size.y;j++){
		if(g->graph[maxX][j]!=NULL){
				rowFree=false;
				break;
			}
		}
	}
	maxX+=2;
	for(int i=++maxX;i<g->size.y;i++){
		free(g->graph[i]);
	}
	g->size.x=maxX;
	if(g->one->loc.x!=g->size.x/2)	MoveNode(g, g->one->loc.x, g->one->loc.y, g->size.x/2, g->one->loc.y);
}

//	-----------------------------------------------------------------------------------------------------
//	Funkce Cudd_GraphMake vytvoří a vygeneruje graf Tuto funkci je nutné zavolat před jakýmikoliv dalšími 
//	operacemi s grafem. Jako první parametr vyžaduje ukazatel na struktru GRAPH. Tato struktura nesmí být 
//	alokována, funkce si jí alokuje sama. Druhý parametr je ukazatel na strukturu DdManager, která obsahuje BDD,
//	jež se má vykrestlit. Třetí parametr je pole ukazatelů na kořeny BDD. Čtvrtý a páty parametr udává počet 
//	vstupních resp. výstupních proměnných funkcí výstupů. Parametr oNames je pole ukazatelů na názvy vstupních 
//	proměnných a poslední parametr je pole ukazatelů názvů vstupních proměnných.

bool Cudd_GraphMake(GRAPH *g, DdManager *manager, DdNode **f, int out, int in, char **oNames, char **iNames){
	char buffer[10];
	int shareX=0;
	PNODE pNode;
	bool free=true;
	Cudd_GraphDelete(g);
	INSNODE *pIns;
	InitGraph(g, NULL, (Cudd_SharingSize(f, out)+1)*3, in+3);
	g->one->loc.x=0;
	g->one->loc.y=g->size.y-1;
	g->graph[0][g->size.y-1]=g->one;
	for(int i=0;i<out;i++){
		pNode=(NODE *) malloc(sizeof(NODE));
		pNode->comp=Cudd_IsComplement(f[i]);
		if(oNames!=NULL) {
			pNode->name=(char *)malloc(sizeof(char)*strlen(oNames[i]));
			strcpy(pNode->name, oNames[i]);
		}
		else{
			itoa(i, &buffer[1], 10);
			buffer[0]='f';
			itoa(i, &buffer[1], 10);
			pNode->name=(char *)malloc(sizeof(char)*strlen(buffer));
			strcpy(pNode->name, buffer);
		}
		pNode->type=1;
		pNode->loc.y=0;
		pNode->pElse=LoadSubGraph(g, f[i], &shareX, iNames,1, Cudd_IsComplement(f[i])?5:4);
		shareX++;
		pNode->pThen=pNode->pElse;
		pNode->loc.x=pNode->pThen->loc.x;
		g->graph[pNode->loc.x][0]=pNode;
		pNode->pElse=InsertDummy(g, pNode->pThen, pNode->loc.x, 0, Cudd_IsComplement(f[i])?5:4);
		pIns=g->inserted;
		while(pIns->next!=NULL) pIns=pIns->next;
		pIns->next=(INSNODE *)malloc(sizeof(INSNODE));
		pIns=pIns->next;
		pIns->next=NULL;
		pIns->newNode=pNode;
		pIns->pBDNode=NULL;
	}
	FreeUnused(g);
	return true;
}

//	--------------------------------------------------------------------------------------------------------
// Funkce Cudd_GraphSavePs uloží diagram do souboru typu PostScript. Druhý parametr je cesta cílového soboru

void Cudd_GraphSavePs(GRAPH *g, char *path){
	POINT point, rectBegin, rectEnd, rectChildBegin, rectChildEnd, oldShift=g->shift;
	FILE *f=fopen(path, "w");
	g->shift.x=0;
	g->shift.y=0;

	fprintf(f, "%%!PS­Adobe­2.0\n");
	fprintf(f, "%%%%Creator: VizBdd\n");
	fprintf(f, "%%%%Title: BDD\n");
	fprintf(f, "%%%%For: (Adobe Developer Support)\n");
	fprintf(f, "%%%%BoundingBox: 0 0 %d %d\n", PSSIZEX, PSSIZEY);
	fprintf(f, "%%%%Pages: 1\n");
	fprintf(f, "%%%%+ font Courier\n");
	fprintf(f, "%%%%EndComments\n");
	fprintf(f, "/Courier findfont\n%d scalefont\n setfont\n", 20);
	int shiftY=PSSIZEY;
	float scale=0,scale2=0;
	if(g->size.x*g->grid>PSSIZEX) {
		if(g->size.y*g->grid>PSSIZEY){
			scale=MIN((float)PSSIZEY/((float)g->size.y*g->grid), (float)PSSIZEX/((float)(g->size.x)*g->grid));	
		}
		else scale=(float)PSSIZEX/(((float)g->size.x)*g->grid);
	}
		
	if(scale>0)	{
		shiftY=(int)((float)shiftY*(1/scale));
		fprintf(f, "%f %f scale\n ", scale, scale);
	}
	fprintf(f, "%i 0 translate\n", g->grid);
	for(int i=0;i<g->size.x;i++)
		for(int j=0;j<g->size.y;j++)
			if(g->graph[i][j]!=NULL){
				// Vykresli ctverec a vypise Index
				point.x=i;
				point.y=j;
				GetNameRect(g, point, &rectBegin, &rectEnd);
				if(g->graph[i][j]->type<=1){
					fprintf(f, "newpath\n");
					fprintf(f, "%d %d moveto\n", rectBegin.x+g->border/2, shiftY-rectEnd.y+g->border/2+2);
					fprintf(f, "(%s) show\n", g->graph[i][j]->name);
					fprintf(f, "%d %d moveto\n", rectBegin.x, shiftY-rectEnd.y);
					fprintf(f, "%d %d lineto\n", rectBegin.x,shiftY-rectBegin.y);
					fprintf(f, "%d %d lineto\n", rectEnd.x,shiftY-rectBegin.y);
					fprintf(f, "%d %d lineto\n", rectEnd.x, shiftY-rectEnd.y);
					fprintf(f, "%d %d lineto\n", rectBegin.x, shiftY-rectEnd.y);
					fprintf(f, "stroke\n");
				}
				else rectEnd.y=rectBegin.y;
				// nakresli caru k naslednikum
				if(g->graph[i][j]!= g->one){
					if(g->graph[i][j]->type==3 || g->graph[i][j]->type==0  || ((g->graph[i][j]->type==4 || g->graph[i][j]->type==1)&& g->graph[i][j]->comp==true)){
						if(g->graph[i][j]->comp) {
							fprintf(f, "[3] 0 setdash\n");
							fprintf(f, "1 0 0 setrgbcolor\n");
						}
						else {
							fprintf(f, "[10 5] 0 setdash\n");
							fprintf(f, "0 0 1 setrgbcolor\n");
						}
					}
					point=g->graph[i][j]->pElse->loc;
					GetNameRect(g, point, &rectChildBegin, &rectChildEnd);
					fprintf(f, "newpath\n");
					fprintf(f, "%d %d moveto\n", rectBegin.x+(rectEnd.x-rectBegin.x)/2, shiftY-rectEnd.y);
					fprintf(f, "%d %d lineto\n", rectChildBegin.x+(rectChildEnd.x-rectChildBegin.x)/2, shiftY-rectChildBegin.y);
					fprintf(f, "stroke\n");
					fprintf(f, "[] 0 setdash\n");
					fprintf(f, "0 0 0 setrgbcolor\n"); 
					if(g->graph[i][j]->type) continue;
					fprintf(f, "newpath\n");
					point=g->graph[i][j]->pThen->loc;
					GetNameRect(g, point, &rectChildBegin, &rectChildEnd);
					fprintf(f, "%d %d moveto\n", rectBegin.x+(rectEnd.x-rectBegin.x)/2, shiftY-rectEnd.y);
					fprintf(f, "%d %d lineto\n", rectChildBegin.x+(rectChildEnd.x-rectChildBegin.x)/2, shiftY-rectChildBegin.y);
					fprintf(f, "stroke\n");
				}
			}
	fprintf(f, "showpage\n");
	g->shift=oldShift;
	fclose(f);
}

//	-------------------------------------------------------
// Funkce GraphDelete smaže graf a uvolní alokovanou paměť
void Cudd_GraphDelete(GRAPH *g){
	INSNODE *next=g->inserted, *del;
	g->inserted=NULL;
	while (next!=NULL){
		del=next;
		next=next->next;
		free(del);
	}
	if(g->graph==NULL) return;
	for(int i=0;i<g->size.x;i++){
		for(int j=0;j<g->size.y;j++){
			if(g->graph[i][j]!=NULL) {
				free(g->graph[i][j]);
			}
		}
		free(g->graph[i]);
	}
	free(g->graph);
	g->graph=NULL;
}

//	------------------------------------------------------------------
//	Funkce Cudd_GraphEvaluate ohodnotí, čímž vyjádří jeho "čitelnost"
//	pokud je druhy paramter nastaven na true, do hodnoceni se nezapocitavaji 
//	delky hran, jez vedou od korenu
double Cudd_GraphEvaluate(GRAPH *g, bool ignored){
	POINT A,B;
	unsigned long crossing=0;
	double lineLength=0;
	double final;
	unsigned int U=0;
	unsigned long nodeCrossing=0;
	//spocita kolik hran se krizi a jestli nejaka hrana neprochazi uzlem
	INSNODE *iter=g->inserted;
	INSNODE *iter2;
	while(iter!=NULL && iter->next!=NULL){
		iter2=iter->next;
		while(iter2!=NULL){
			if(!iter->newNode->type){
				if(!iter2->newNode->type){
					if(Crossing(iter->newNode->loc, iter->newNode->pThen->loc, iter2->newNode->loc, iter2->newNode->pThen->loc)) crossing++;
				}
				if(Crossing(iter->newNode->loc, iter->newNode->pThen->loc, iter2->newNode->loc, iter2->newNode->pElse->loc)) crossing++;
			}
			if(!iter2->newNode->type) 
				if(Crossing(iter->newNode->loc, iter->newNode->pElse->loc, iter2->newNode->loc, iter2->newNode->pThen->loc)) crossing++;			
			if(Crossing(iter->newNode->loc, iter->newNode->pElse->loc, iter2->newNode->loc, iter2->newNode->pElse->loc)) crossing++;
			iter2=iter2->next;
		}
		iter=iter->next;
	}
	iter=g->inserted;
	while(iter!=NULL){
		A=iter->newNode->loc;
		if(iter->newNode->type==0) U++;
		B=iter->newNode->pElse->loc;
		nodeCrossing+=CrossPoint(g, A, B);
		if(!ignored || (iter->newNode->type!=4 && iter->newNode->type!=1)){
			B.x-=A.x;
			B.y-=A.y;
			lineLength+=(sqrt((double)(B.x*B.x+B.y*B.y)));
		}
		if(iter->newNode->type) {
			iter=iter->next;
			
			continue;
		}
		B=iter->newNode->pThen->loc;
		nodeCrossing+=CrossPoint(g, A, B);
		B.x-=A.x;
		B.y-=A.y;
		lineLength+=(sqrt((double)(B.x*B.x+B.y*B.y)));
		iter=iter->next;
	}
	final=((float)(lineLength+crossing*g->size.y)*(nodeCrossing+1))/U;
	return final;
}

// --------------------------------------------------------------------------------------
//	Funkce spocita jak horni, tak dolni teziste uzlu v radku danem parametrem level
//	Vrati pole down resp. up obsahujici hodnoti tezist podle indexu

void Barycenters(GRAPH *g, int level, float *down, float *up){
	int *hitCount=(int *)malloc(sizeof(int)*g->size.x);
	memset(hitCount, 0, sizeof(int)*g->size.x);
	memset(up, 0, sizeof(int)*g->size.x);
	for(int i=0;i<g->size.x;i++){
		if(g->graph[i][level]!=NULL){
			if(g->graph[i][level]->type) {
				down[i]=(float)g->graph[i][level]->pElse->loc.x;
				up[g->graph[i][level]->pElse->loc.x]+=i;
				hitCount[g->graph[i][level]->pElse->loc.x]++;
			}
			else {
				down[i]=abs(((float)g->graph[i][level]->pThen->loc.x+(float)g->graph[i][level]->pElse->loc.x)/2); 
				up[g->graph[i][level]->pElse->loc.x]+=i;
				up[g->graph[i][level]->pThen->loc.x]+=i;
				hitCount[g->graph[i][level]->pElse->loc.x]++;
				hitCount[g->graph[i][level]->pThen->loc.x]++;
			}
		}
		else down[i]=-1;
	}
	for(int i=0;i<g->size.x;i++){
		if(hitCount[i]>0) up[i]/=hitCount[i];
		else up[i]=-1;
	}
}

// --------------------------------------------------------------------------------------
//	funkce seradi na radku danem param. level uzly v poradi danem polem in (polem tezist)

bool SortByBarycenters(GRAPH *g, int level, float *in){
	bool move=false;
	float min;
	int mininx;
	for(int i=0;i<g->size.x;i++){
		if(in[i]<0) continue;
		min=in[i];
		mininx=i;
		for(int j=i+1;j<g->size.x;j++){
			if(min>in[j] && in[j]>=0){
				min=in[j];
				mininx=j;
			}
		}
		if(min==in[i]) continue;
		move=true;
		min=in[i];
		in[i]=in[mininx];
		in[mininx]=min;
		SwapNode(g, g->graph[i][level], g->graph[mininx][level]);
	}
	return move;
}

// -------------------------------------------------------------------------------------------------
//	funkce vraci true, pokud se (pomyslna)usecka vedena ze souradnice [x][a1] do souradnice [X+1][a2] 
//	s useckou z[X][b1]do [x+1][b2]

bool Cross(int a1, int a2, int b1, int b2){
	if(a2==b2) return false;
	return a1>b1? a2<b2 : a2>b2;
}

// --------------------------------------------------------------------------------------
//	funkce vrati pocet krizeni mezi radky level a level+1
int CrossingCount(GRAPH *g, int level){
	int crossCount=0;
	for(int i=0;i<g->size.x;i++){
		if(g->graph[i][level]!=NULL){
			for(int j=i+1;j<g->size.x;j++){
				if(g->graph[j][level]!=NULL){
					if(!g->graph[i][level]->type){
						if(!g->graph[j][level]->type){
							if(Cross(i, g->graph[i][level]->pThen->loc.x, j, g->graph[j][level]->pThen->loc.x)) crossCount++;	
						}						
						if(Cross(i, g->graph[i][level]->pThen->loc.x, j, g->graph[j][level]->pElse->loc.x)) crossCount++;
					}
					if(!g->graph[j][level]->type) 
						if(Cross(i, g->graph[i][level]->pElse->loc.x, j, g->graph[j][level]->pThen->loc.x)) crossCount++;
				    if(Cross(i, g->graph[i][level]->pElse->loc.x, j, g->graph[j][level]->pElse->loc.x)) crossCount++;
				}
			}
		}
	}
	return crossCount;
}

// ------------------------------------------------------------------------------------------
//	Funkce prochazi pole zdola nahoru a ze shora dolu a radi uzle podle jejich tezist, pokud 
//	tak snizi pocet prekrizenych hran. Parametr maxiter udava maximalni pocet iteraci(pruchodu dolu-nahoru),
//	jez se provedou

void Phase1(GRAPH *g, int maxiter, float *down, float *up){
	POINT *saveLoc=(POINT *)malloc(sizeof(POINT)*g->size.x);
	NODE **saveLine=(PNODE *)malloc(sizeof(PNODE)*g->size.x);
	bool moved;
	int iter=0;	
	int count, count2;
	do{
		moved=false;
		iter++;
		for(int i=g->size.y-2;i>=1;i--){
			count = CrossingCount(g, i);
			for(int j=0;j<g->size.x;j++){
				saveLine[j]=g->graph[j][i];
				if(g->graph[j][i]!=NULL) saveLoc[j]=g->graph[j][i]->loc;
			}	
			Barycenters(g, i, down, up);
			if(SortByBarycenters(g, i, down)) moved=true;
			count2 = CrossingCount(g, i);
			if(count<count2){
				for(int j=0;j<g->size.x;j++){
					g->graph[j][i]=saveLine[j];
					if(g->graph[j][i]!=NULL) g->graph[j][i]->loc=saveLoc[j];
				}
			}
		}
		for(int i=0;i<g->size.y-2;i++){
			count = CrossingCount(g, i);
			//save
			for(int j=0;j<g->size.x;j++){
				saveLine[j]=g->graph[j][i+1];
				if(g->graph[j][i+1]!=NULL) saveLoc[j]=g->graph[j][i+1]->loc;
			}	
			Barycenters(g, i, down, up);
			if(SortByBarycenters(g, i+1, up)) moved=true;
			count2 = CrossingCount(g, i);
			if(count<count2){
				//restore
				for(int j=0;j<g->size.x;j++){
					g->graph[j][i+1]=saveLine[j];
					if(g->graph[j][i+1]!=NULL) g->graph[j][i+1]->loc=saveLoc[j];
				}
			}
		}

	}while(moved && iter<maxiter);
	free(saveLine);
	free(saveLoc);
}

// ---------------------------------------------------------------------------------------------
//	Tato funkce krome volani funkce Phase1 prehazuje uzly se stejnym tezistem{a opet vola Phase1)

void CrossMinBarycenters(GRAPH *g, int maxiter, int maxiter2){

	float *up=(float *) malloc(g->size.x*sizeof(float));
	float *down=(float *) malloc(2*g->size.x*sizeof(float));
	int iter2=0;

	do{
		iter2++;
		Phase1(g, maxiter, down, up);
		for(int i=g->size.y-2;i>=1;i--){
			Barycenters(g, i-1, down, up);
			for(int j=0;j<g->size.x-1;j++){
				if(up[j]==up[j+1] && up[j]>=0) {
					SwapNode(g, g->graph[j][i], g->graph[j+1][i]);
					Barycenters(g, i, down, up);
					for(int k=0;k<g->size.x-1;k++){
						if(up[k]>up[k+1] && up[k]>=0){
							Phase1(g, maxiter, down, up);
							break;
						}	
					}
				Barycenters(g, i-1, down, up);
				}
			}
		}
		for(int i=1;i<g->size.y-1;i++){
			Barycenters(g, i, down, up);
			for(int j=0;j<g->size.x-1;j++){
				if(down[j]==down[j+1] && down[j]>=0) {
					SwapNode(g, g->graph[j][i], g->graph[j+1][i]);
					Barycenters(g, i-1, down, up);
					for(int k=0;k<g->size.x-1;k++){
						if(up[k]>up[k+1] && up[k]>=0){
							Phase1(g, maxiter, down, up);
							break;
						}	
					}
					Barycenters(g, i, down, up);
				}
			}
		}
	}while(iter2<maxiter2);
	free(up);
	free(down);
}

// ---------------------------------------------------------------------------------------------
//	Funkce umistuje prvne falesne uzly a pak normalni uzly na mista jejich tezist

bool ReduceLineLength(GRAPH *g){
	float *up=(float *) malloc(g->size.x*sizeof(float));
	float *down=(float *) malloc(2*g->size.x*sizeof(float));
	bool moved=false;
	int destX;
	for(int i=1;i<g->size.y-1;i++){
		Barycenters(g, i-1, down, up);
		for(int j=g->size.x-1;j>=0;j--){
			if(g->graph[j][i]!=NULL){
				if(g->graph[j][i]->type){
					destX=(int)up[j];
					while(g->graph[destX][i]!=NULL && destX>0) destX--;
					if(destX>j){
						MoveNode(g, j, i, destX, i);
						moved=true;
					}

				}
			}
		}
	}
	for(int i=g->size.y-2;i>=0;i--){
		for(int j=g->size.x-1;j>=0;j--){
			if(g->graph[j][i]!=NULL){
				if(g->graph[j][i]->type) {
					destX=g->graph[j][i]->pElse->loc.x;
					while(g->graph[destX][i]!=NULL && destX>0) destX--;
					if(destX>j){
						MoveNode(g, j, i, destX, i);
						moved=true;
					}
				}
			}
		}
	}
	for(int i=1;i<g->size.y-1;i++){
		Barycenters(g, i-1, down, up);
		for(int j=g->size.x-1;j>=0;j--){
			if(g->graph[j][i]!=NULL){
				if(g->graph[j][i]->type<=1){
					destX=(int)up[j];
					while(g->graph[destX][i]!=NULL && destX>0) destX--;
					if(destX>j){
						MoveNode(g, j, i, destX, i);
						moved=true;
					}
				}
			}
		}
	}
	for(int i=g->size.y-2;i>=0;i--){
		Barycenters(g, i, down, up);
		for(int j=g->size.x-1;j>=0;j--){
			if(g->graph[j][i]!=NULL){
				if(g->graph[j][i]->type<=1) {
					destX=(int)down[j];
					while(g->graph[destX][i]!=NULL && destX>0) destX--;
					if(destX>j)	{
						MoveNode(g, j, i, destX, i);
						moved=true;
					}
				}
			}
		}
	}
	return moved;
}


// -------------------------------------------------------------------------------
//	Funkce umistuje prvne falesne uzly a pak normalni uzly na mista jejich tezist
bool Greed(GRAPH *g){
	double oldEval, newEval;
	oldEval=Cudd_GraphEvaluate(g, true);
	bool move=false;
	for(int i=0;i<g->size.y-1;i++){
		for(int j=g->size.x-1;j>=0;j--){
			if(g->graph[j][i]!=NULL){		
				if(g->graph[j][i]->type==4 || g->graph[j][i]->type==1){
					if(j>=g->graph[j][i]->pThen->loc.x) continue;
					move=true;
				}
				if(g->graph[j+1][i]==NULL) MoveNode(g, j, i, j+1, i);
					else SwapNode(g, g->graph[j][i], g->graph[j+1][i]); 
				newEval=Cudd_GraphEvaluate(g, true);
				if(oldEval<newEval){
					if(g->graph[j][i]==NULL) MoveNode(g, j+1, i, j, i);
						else SwapNode(g, g->graph[j][i], g->graph[j+1][i]);
				}
				else{
					if(oldEval>newEval) move=true;
					oldEval=newEval;
					
				}
			}
		}
	}

	return move;
}
	

// -------------------------------------------------------------------------------
//	Funkce Cudd_GraphOptimalize optimalizuje graf. parametr udává funkci, jednu z dvou metod, 
//	jež se má pro optimalizaci použít. Možné hodnoty tohoto parametru jsou MD_GREEDa MD_BARYCENTERS
void Cudd_GraphOptimalize(GRAPH *g, int method, int iter){
	bool free=true;
	int count=0;
	INSNODE *ignore=NULL;
	if(method==MD_BARYCENTERS){
		Shrink(g);
		FreeUnused(g);
		CrossMinBarycenters(g, iter, iter);	
		while(ReduceLineLength(g) && count<iter) count++;
		FreeUnused(g);
	}
	if(method==MD_GREED){
		Shrink(g);
		FreeUnused(g);
		while(Greed(g) && count<iter*10) count++;
		count=0;
		while(count<g->size.y && DelDummy(g)) count++;
		FreeUnused(g);
		
	}
}
