/*
graph.c
Pedro Flynn - pflynn@microsoftsucks.org
*/

#include <stdlib.h>
#include <string.h>

#include "graph.h"
#include "list.h"
#include "set.h"

Graph* graph_create(int (*match)(const void*,const void*),void (*destroy)(void*))
{
Graph* graph;
	
	if(!(graph = (Graph*) malloc(sizeof(Graph))))
		return NULL;
	
	graph->vcount = graph->ecount = 0;
	graph->match = match;
	graph->destroy = destroy;
	graph->adjlists = list_create(NULL);
	
	return graph;
}

void graph_destroy(Graph* graph)
{
AdjList* adjlist;
	
while(LIST_SIZE(graph->adjlists)){
	
	if(!list_rem_next(graph->adjlists,NULL,(void**) &adjlist)){
		
		set_destroy(adjlist->adjacent);
		
		if(graph->destroy)
			graph->destroy(adjlist->vertex);
	  
		free(adjlist);
	}
	
}

list_destroy(graph->adjlists);

return;	
}


int graph_ins_vertex(Graph* graph,const void* data)
{
ListElmt* element;
AdjList* adjlist;
int retval;
	
for(element = LIST_HEAD(graph->adjlists);element;element = LIST_NEXT(element))
	if(graph->match(data,( (AdjList*) LIST_DATA(element))->vertex))
		return 1;
	
if(!(adjlist = (AdjList*) malloc(sizeof(adjlist))))
	return -1;

adjlist->vertex = (void*) data;
adjlist->adjacent = set_create(graph->match,NULL);

if(!list_ins_next(graph->adjlists,LIST_TAIL(graph->adjlists), adjlist))
	return retval = - 1;

graph->vcount++;

return retval = 0;

}

int graph_ins_edge(Graph* graph,const void* data1,const void* data2)
{
ListElmt* element;
int retval;
	
for(element = LIST_HEAD(graph->adjlists);element;element = LIST_NEXT(element))
	if(graph->match(data2,((AdjList*) LIST_DATA(element))->vertex))
		break;
	
if(!element)
	return  -1;

for(element = LIST_HEAD(graph->adjlists);element;element = LIST_NEXT(element))
	if(graph->match(data1,((AdjList*) LIST_DATA(element))->vertex))
		break;
	
	if(!element)
		return -1;
	
	if(retval = set_insert_element(((AdjList*) LIST_DATA(element))->adjacent,data2))
		return retval;
	
	graph->ecount++;
	
	return retval;

}


int graph_rem_vertex(Graph* graph,void** data)
{
ListElmt *element,*temp,*prev;
AdjList* adjlist;	
int found;
	
prev = NULL;
found = 0;
	
for(element = LIST_HEAD(graph->adjlists);element;element = LIST_NEXT(element)){
	
	if(set_is_member(((AdjList*) LIST_DATA(element))->adjacent,*data))
		return -1;
	
	if(graph->match( ((AdjList*) LIST_DATA(element))->vertex,*data ) ){
  	found = 1;
    temp = element;	
	}
	
	if(!found)
		prev = element;
}

  if(!found)
		return -1;
	
	if(SET_SIZE(((AdjList*) LIST_DATA(temp))->adjacent))
		return -1;
	
	
	if(list_rem_next(graph->adjlists,prev,(void**) &adjlist))
		return -1;
	
	*data = adjlist->vertex;
	
	free(adjlist);
	
	graph->vcount--;
	
	return 0;
	
}

int graph_rem_edge(Graph* graph,const void* data1,void** data2)
{
ListElmt* element;
	
for(element = LIST_HEAD(graph->adjlists);element;element = LIST_NEXT(element))
	if(graph->match(((AdjList*) LIST_DATA(element))->vertex,data1))
		break;
	
if(!element)
	return -1;

if(set_remove_element(((AdjList*) LIST_DATA(element))->adjacent,data2))
	return -1;

graph->ecount--;

return 0;

}


int graph_adjlist(const Graph* graph,const void* data,AdjList** adjlist)
{
ListElmt* element;
	

for(element = LIST_HEAD(graph->adjlists);element;element = LIST_NEXT(element))
	if(graph->match(((AdjList*) LIST_DATA(element))->vertex,data))
		break;
	
	
	


if(!element)
	return -1;

*adjlist = LIST_DATA(element);

return 0;

}


int graph_is_adjacent(const Graph* graph,const void* data1,const void* data2)
{
	ListElmt* element;
	
	
	for(element = LIST_HEAD(graph->adjlists);element;element = LIST_NEXT(element))
		if(graph->match(((AdjList*) LIST_DATA(element))->vertex,data1))
			break;
		
	if(!element)
		return -1;
	
	return set_is_member(((AdjList*) LIST_DATA(element))->adjacent,data2);
	
}