#include <stdio.h>
#include <stdlib.h>
#include "graph.h"

#define TRUE	1
#define FALSE	0

void Graph_Init(tGraph *pGraph)
{
	List_Init(&pGraph->Nodes);
	List_Init(&pGraph->Edges);
}

tList *Graph_GetNodes(tGraph *pGraph)
{
	return (&pGraph->Nodes);
}

tList *Graph_GetEdges(tGraph *pGraph)
{
	return (&pGraph->Edges);
}

int Graph_GetNumNodes(tGraph *pGraph)
{
	return (List_GetCount(&pGraph->Nodes));
}

int Graph_GetNumEdges(tGraph *pGraph)
{
	return (List_GetCount(&pGraph->Edges));
}

tNode *Graph_AddNode(tGraph *pGraph, void *pContent)
{
	tNode *pNode;

	pNode = (tNode *) malloc(sizeof(tNode));
	if (pNode == NULL) {
		fprintf(stderr, "Error: out of memory!\n");
		exit(1);
	}
	pNode->pContent = pContent;
	List_Init(&pNode->OutEdges);
	List_Init(&pNode->InEdges);
	List_AddTail(&pGraph->Nodes, pNode);
	return (pNode);
}

tEdge *Graph_AddEdge(tGraph *pGraph, tNode *pSrc, tNode *pDest)
{
	tEdge *pEdge;
	tList *pOutEdges;
	tPosition pos;

	pOutEdges = Node_GetOutEdges(pSrc);
	pos = List_GotoHead(pOutEdges);
	while (pos != NULL) {
		pEdge = List_GetNext(pOutEdges, &pos);
		if (pEdge->pDest == pDest)
			return (pEdge);
	}
	pEdge = (tEdge *) malloc(sizeof(tEdge));
	if (pEdge == NULL) {
		fprintf(stderr, "Error: out of memory!\n");
		exit(1);
	}
	pEdge->pSrc = pSrc;
	pEdge->pDest = pDest;
	List_AddHead(&pGraph->Edges, pEdge);
	List_AddHead(&pSrc->OutEdges, pEdge);
	List_AddHead(&pDest->InEdges, pEdge);
	return (pEdge);
}

void Graph_RemoveEdge(tGraph *pGraph, tEdge *pEdge)
{
	tPosition pos;
	tList *pList;
	tNode *pSrcNode;
	tNode *pDestNode;

	pList = Graph_GetEdges(pGraph);
	pos = List_Find(pList, pEdge);
	List_RemoveAt(pList, pos);
	pSrcNode = Edge_GetSrcNode(pEdge);
	pList = Node_GetOutEdges(pSrcNode);
	pos = List_Find(pList, pEdge);
	List_RemoveAt(pList, pos);
	pDestNode = Edge_GetDestNode(pEdge);
	pList = Node_GetInEdges(pDestNode);
	pos = List_Find(pList, pEdge);
	List_RemoveAt(pList, pos);
	free(pEdge);
}

void Graph_UnmarkNodes(tGraph *pGraph)
{
	tList *pNodes;
	tPosition pos;
	tNode *pNode;

	pNodes = Graph_GetNodes(pGraph);
	pos = List_GotoHead(pNodes);
	while (pos != NULL) {
		pNode = List_GetNext(pNodes, &pos);
		pNode->bMark = FALSE;
	}
}

int Graph_DepthFirstForward(tGraph *pGraph, tNode *pNode, tVisitFunc *pPreFunc, void *pPreArgs, tVisitFunc *pPostFunc, void *pPostArgs)
{
	tList *pOutEdges;
	tPosition pos;
	tNode *pChild;

	if (pNode->bMark)
		return (FALSE);
	pNode->bMark = TRUE;
	if (pPreFunc != NULL)
		if ((*pPreFunc)(pNode, pPreArgs))
			return (TRUE);
	pOutEdges = &pNode->OutEdges;
	pos = List_GotoHead(pOutEdges);
	while (pos != NULL) {
		pChild = Edge_GetDestNode(List_GetNext(pOutEdges, &pos));
		if (Graph_DepthFirstForward(pGraph, pChild, pPreFunc, pPreArgs, pPostFunc, pPostArgs))
			return (TRUE);
	}
	if (pPostFunc != NULL)
		return ((*pPostFunc)(pNode, pPostArgs));
	else
		return (FALSE);
}

int Graph_DepthFirstBackward(tGraph *pGraph, tNode *pNode, tVisitFunc *pPreFunc, void *pPreArgs, tVisitFunc *pPostFunc, void *pPostArgs)
{
	tList *pInEdges;
	tPosition pos;
	tNode *pParent;

	if (pNode->bMark)
		return (FALSE);
	pNode->bMark = TRUE;
	if (pPreFunc != NULL)
		if ((*pPreFunc)(pNode, pPreArgs))
			return (TRUE);
	pInEdges = &pNode->InEdges;
	pos = List_GotoHead(pInEdges);
	while (pos != NULL) {
		pParent = Edge_GetSrcNode(List_GetNext(pInEdges, &pos));
		if (Graph_DepthFirstBackward(pGraph, pParent, pPreFunc, pPreArgs, pPostFunc, pPostArgs))
			return (TRUE);
	}
	if (pPostFunc != NULL)
		return ((*pPostFunc)(pNode, pPostArgs));
	else
		return (FALSE);
}

tNode *Graph_FindNode(tGraph *pGraph, void *pContent)
{
	tList *pNodes;
	tNode *pNode;
	tPosition pos;

	pNodes = &pGraph->Nodes;
	pos = List_GotoHead(pNodes);
	while (pos != NULL) {
		pNode = List_GetNext(pNodes, &pos);
		if (pNode->pContent == pContent)
			return (pNode);
	}
	return (NULL);
}

static int Graph_AddQueue(tNode *pNode, tList *pQueue)
{
	List_AddTail(pQueue, pNode);
	return (FALSE);
}

void Graph_CalcSccListList(tGraph *pGraph, tList *pListList)
{
	tList Queue;
	tList *pNodes;
	tPosition pos;
	tNode *pNode;
	tList *pList;

	List_Init(&Queue);
	Graph_UnmarkNodes(pGraph);
	pNodes = Graph_GetNodes(pGraph);
	pos = List_GotoHead(pNodes);
	while (pos != NULL) {
		pNode = List_GetNext(pNodes, &pos);
		Graph_DepthFirstForward(pGraph, pNode, NULL, NULL, Graph_AddQueue, &Queue);
	}
	Graph_UnmarkNodes(pGraph);
	while ((pNode = List_RemoveTail(&Queue)) != NULL)
		if (!Node_IsMarked(pNode)) {
			pList = (tList *) malloc(sizeof(tList));
			List_Init(pList);
			Graph_DepthFirstBackward(pGraph, pNode, Graph_AddQueue, pList, NULL, NULL);
			List_AddHead(pListList, pList);
		}
}

void *Node_GetContent(tNode *pNode)
{
	if (pNode == NULL)
		return (NULL);
	else
		return (pNode->pContent);
}

tList *Node_GetOutEdges(tNode *pNode)
{
	return (&pNode->OutEdges);
}

tList *Node_GetInEdges(tNode *pNode)
{
	return (&pNode->InEdges);
}

int Node_GetOutDegree(tNode *pNode)
{
	return (List_GetCount(&pNode->OutEdges));
}

int Node_GetInDegree(tNode *pNode)
{
	return (List_GetCount(&pNode->InEdges));
}

int Node_IsMarked(tNode *pNode)
{
	return (pNode->bMark);
}

tNode *Edge_GetSrcNode(tEdge *pEdge)
{
	return (pEdge->pSrc);
}

tNode *Edge_GetDestNode(tEdge *pEdge)
{
	return (pEdge->pDest);
}