#include "global.h"
#include "cgraph.h"
#include "cmemory.h"
#include <stdlib.h>
#include "cstack.h"
#include "capp.h"

CGraph::CGraph(DWORD n)
{
	Create(n);
}

void CGraph::Create(DWORD n)
{
	nVertexs = n;
	vertexs = _NEW(CMemory());
	vertexs->AddData(NULL, sizeof(GRAPH_VERTEX)*n);

	CMemory **v = (CMemory**)vertexs->GetPointer();
	for (DWORD i=0; i<n; i++)
	{
		//vytvor novy vrchol
		v[i] = _NEW(CMemory());
		v[i]->AddData(NULL, sizeof(GRAPH_VERTEX));
		GRAPH_VERTEX *ver = (GRAPH_VERTEX*)v[i]->GetPointer();
		ver->nArc = 0;
		ver->value = 0;//user defined value
		ver->id = i;
	}
}

CGraph::CGraph(const SYNTACTIC_TABLE_RULES* table)
{
	Create(table->nIdb);

	//prirad vrcholom grafu ID z rulestable
	DWORD j=0;//cislo vrchola
	for (DWORD i=table->nEdb; i<table->nAtoms; i++)
	{
		SYNTACTIC_ATOM *a = table->atoms[i];
		if ( (a->edb.type == SYNTACTIC_ATOM_IDBATOM) || (a->edb.type == SYNTACTIC_ATOM_ANSWER) )
		{
			GetVertex(j)->id = i;
			j++;
		}
	}

	for (i=0; i<nVertexs; i++)
	{
		GRAPH_VERTEX* v = GetVertex(i);
		SYNTACTIC_ATOM *a = table->atoms[v->id];
		if ( (a->edb.type == SYNTACTIC_ATOM_IDBATOM) || (a->edb.type == SYNTACTIC_ATOM_ANSWER) )
		{
			for (DWORD j=0; j<a->idb.nRules; j++)
			{
				//pre kazdy relacny idb atom (podciel) na pravej strane pridaj hranu z hlavicky 
				for (DWORD k=0; k<a->idb.rules[j]->nAtoms; k++)
				{
					DWORD id = a->idb.rules[j]->atom[k]->id;
					if (table->atoms[id]->idb.type == SYNTACTIC_ATOM_IDBATOM)
					{
						AddArc(i, GetVertexIndexByID(id));//pridaj sipku
					}
				}
			}
		}
	}
}

DWORD CGraph::GetnVertexs()
{
	return nVertexs;
}

void CGraph::ClearAllValues()
{
	CMemory **v = (CMemory**)vertexs->GetPointer();
	for (DWORD i=0; i<nVertexs; i++)
		((GRAPH_VERTEX*)v[i]->GetPointer())->value = 0;
}

CMemory *CGraph::TopologicalSort(DWORD rootID, bool loopStop)
{
	ClearAllValues();
	CMemory *list = _NEW(CMemory());
	CStack *stack = _NEW(CStack());

	CMemory **m = (CMemory**)vertexs->GetPointer();

	stack->Push(0);//pred id vrchola syna si otec uklada jeho poradie medzi jeho surodencami
	stack->Push(GetVertexIndexByID(rootID));//na zasobnik ide cislo vrchola (nie ID)
	DWORD last = 0;//na zaciatku sa prehladava od prveho syna

	while (!stack->Empty())
	{
		GRAPH_VERTEX *v,*v2;

		DWORD top = stack->Top();//id vrchola

		DWORD next = -1;
		//prejdi vsetky deti vrchola top a chod tam, kde sme este neboli
		v = (GRAPH_VERTEX*)m[top]->GetPointer();
		v->value = 1;//vrchol bol navstiveny
		for (DWORD i=last; i<v->nArc; i++)
		{
			v2 = ((GRAPH_VERTEX*)(m[v->arcs[i]]->GetPointer()));
			if (v2->value)
			{
				//tento vrchol sme uz predtym na nasej ceste navstivili - CYKLUS
				if (loopStop)
				{
					_DELETE(list); _DELETE(stack);
					return NULL;
				}
				else
				{
					continue;//zober dalsi vrchol
				}
			}
			else
			{
				//tu sme este neboli
				next = v->arcs[i];
				break;
			}
		}

		if (next!=-1)
		{
			//ideme do dalsieho vrchola
			stack->Push(i+1);//zapamatame si, od ktoreho syna mame pri navrate pokracovat
			stack->Push(next);
			last = 0;//prehladavaj synov od zaciatku
			continue;
		}
		else
		{
			//nemame kam ist
			//opustame vrchol, nasa cesta z roota uz cezen nepojde

			//pridaj vrchol do vystupu (ak tam uz je, nepridaj ho)
			if (!list->GetSize())
				//list je prazdny, pridaj prvy vrchol
				list->AddData(&top, 4);
			else
			{
				bool insert = true;
				for (DWORD i=0; i<list->GetSize()/4; i++)
				{
					if (PTR(DWORD*,list)[i] == top)
					{
						insert = false;//uz je v zozname
						break;
					}
				}
				if (insert)
					list->AddData(&top, 4);
			}
			stack->Pop();//vymaz vrchol
			last = stack->Pop();//pokracuj v prehladavani dalsieho syna
			v->value = 0;
		}
	}

	_DELETE(stack);

	return list;
}

GRAPH_VERTEX *CGraph::GetVertex(DWORD i)
{
	if (i<nVertexs)
	{
		CMemory *mem = (CMemory*)((DWORD*)(vertexs->GetPointer()))[i];
		return (GRAPH_VERTEX*)(mem->GetPointer());
	}
	else
	{
#ifdef _DEBUG
		::MessageBox(0, "id>=nVertexs", "CGraph::GetVertex(id)", MB_ICONSTOP|MB_OK);
#endif
		app.abort();
		return NULL;//kvoli warningu
	}
}

DWORD CGraph::GetVertexIndexByID(DWORD id)
{
	for (DWORD i=0; i<nVertexs; i++)
	{
		GRAPH_VERTEX* ver = (GRAPH_VERTEX*)((CMemory*)((DWORD*)(vertexs->GetPointer()))[i])->GetPointer();
		if (ver->id == id)
			return i;
	}
#ifdef _DEBUG
	::MessageBox(0, "Vrchol s daným ID neexistuje!", "CGraph::GetVertexIndexByID(id)", MB_ICONSTOP|MB_OK);
#endif
	app.abort();
	return -1;//kvoli warningu
}

CGraph::~CGraph()
{
	CMemory **v = (CMemory**)vertexs->GetPointer();
	for (DWORD i=0; i<nVertexs; i++)
	{
		_DELETE(v[i]);
	}
	_DELETE(vertexs);
}

void CGraph::AddArc(DWORD fromVer,DWORD toVer)
{
	if ( (fromVer<nVertexs) || (toVer<nVertexs) )
	{
		CMemory *from = (CMemory*)(((DWORD*)(vertexs->GetPointer()))[fromVer]);
		//neexistuje uz tato hrana?
		bool najdene = false;
		for (DWORD i=0;i<PTR(GRAPH_VERTEX*,from)->nArc; i++)
		{
			if (PTR(GRAPH_VERTEX*,from)->arcs[i] == toVer)
			{
				najdene = true;
				break;
			}
		}
		if (!najdene)
		{
			//este neexistuje
			from->AddData(&toVer, 4);
			PTR(GRAPH_VERTEX*,from)->nArc++;
		}
	}
	else
	{
#ifdef _DEBUG
		::MessageBox(0, "Číslo vrcholov je väčšie ako ich počet", "CGraph::AddArc", MB_ICONSTOP|MB_OK);
#endif
		app.abort();
	}
}
