#ifndef GMAP_C
#define GMAP_C GMAP_C
#include <map.h>



/*
 *	ID and residue and all of delta is assigned to NULL
 * */
void Map_Init(Map *tree)
{
	tree->is_final=0;
	for(int i=0;i<256;++i)tree->delta[i] = NULL;
	tree->ID = NULL;
} 

void Map_Scour(Map *tree,void *str,size_t size,size_t *where,Map **final_node)
{
	for(
		 *where=0,*final_node=tree;
		*where<size && final_node[0]->delta[((unsigned char*)str)[ where[0] ]]!=NULL;
		++where[0]
	)
	{
		(*final_node) = (*final_node)->delta[((unsigned char*)str)[*where]];
	}
}



/*
 * tree must not be null	
 * */
void Map_Push(Map *tree,void *str,size_t size,void *id)
{
	size_t temp;
	Map_Scour(tree,str,size,&temp,&tree);	

	if(temp == size)
	{
		assert(tree->ID==NULL);
		tree->ID=id;
		tree->is_final=1;
		return;
	}
	for(temp;temp<size;++temp)
	{
		tree=tree->delta[((unsigned char*)str)[temp]]=calloc(1,sizeof(Map));
		/*
		Map_Init(
			tree=tree->delta[((unsigned char*)str)[temp]]=malloc(sizeof(Map))
			);
			*/
	}

	tree->ID=id;
	tree->is_final=1;

}


/*
 * 	scours the tree and returns the id of the node that recognises the str
 * 	returns NULL if the string is not recognised
 * */
void* Map_Check(Map *tree, void *str,size_t size)
{
	size_t temp;
	Map_Scour(tree,str,size,&temp,&tree);

	if(temp<size)
	{
		return NULL;	
	}else
	{
		return tree->ID; //this has been set to be the last reached node
	}
}

void Map_Remove(Map *tree, void *str,size_t size)
{
	Stack stk;
	Stack_Init(&stk);
	size_t where;
	char what_to_null=((char*)str)[0];

	Stack_Push(&stk,tree);

	for(where=0;where<size-1 && tree->delta[((unsigned char*)str)[where]]!=NULL;++where)
	{
		tree = tree->delta[((unsigned char*)str)[where]];
		if(tree->is_final==1)
		{
			while(stk.size>0)Stack_Pop(&stk);
			what_to_null=((char*)str)[where+1];
		}
		Stack_Push(&stk,tree);
	}
	if(tree->delta[((unsigned char*)str)[where]] == NULL)return;
	free(tree->delta[((unsigned char*)str)[where]]);
	while(stk.size>1)free(Stack_Pop(&stk));
	tree=(Map*)Stack_Pop(&stk);
	tree->delta[(unsigned char)what_to_null]=NULL;
	
}
/*This function especially requires that the map has no loops*/
void Map_Map(Map *tree,void (*map)(void*))
{
	if(tree->is_final==1)map(tree->ID);
	for(int i=0;i<256;++i)
	{
		if(tree->delta[i]!=NULL)
		{
			Map_Map(tree->delta[i],map);
		}
	}
}

/*first argument of map is the node id , the second is pass_data*/
void Map_Map_Extended(Map *tree,void (*map)(void*,void*),void* pass_data)
{
	if(tree->is_final==1)map(tree->ID,pass_data);
	for(int i=0;i<256;++i)
	{
		if(tree->delta[i]!=NULL)
		{
			Map_Map_Extended(tree->delta[i],map,pass_data);
		}
	}
}


/*this does not destroy(free) any memory pointed to by a node in the Map. This does not free() the root (Map *tree) */
/*This function especially does not require that the map has no loop ( for example after grepification )*/
void Map_Destroy(Map *tree)
{
	Stack path;
	Stack nodes;
	Map *current_node;
	unsigned int i;
	 

	Stack_Init(&path);
	Stack_Init(&nodes);

	Stack_Push(&path,tree);
	Stack_Push(&nodes,tree);

	/*
	   using DFS we fill up the nodes stack with all the used
	   (accessible) nodes.
	 */
	while(path.size>0)
	{
		current_node=Stack_Pop(&path);
		current_node->ID=&(current_node->ID);/*mark the node*/
		for(i=0;i<256;++i)
		{
			if(current_node->delta[i]!=NULL && current_node->delta[i]->ID != &(current_node->delta[i]->ID) )
			{
				Stack_Push(&path,current_node->delta[i]);


				/*we mark the unmarked child of the current_node*/
				current_node->delta[i]->ID=&(current_node->delta[i]->ID);
				/*every node in nodes continues to be marked*/
				Stack_Push(&nodes,current_node->delta[i]);
			}
		}
		
	}
	/*
	   There should not be any duplicates in here
	 */
	while(nodes.size>1)
	{
		current_node=Stack_Pop(&nodes);
		/*Again the things that ID points to is not freed ( this structure is used to map the structure of data )
		  deletion of it is up to you.
		 */
		free(current_node);
	}
	/*this is where the root is at- we don't delete it , but we must free the last stack node*/
	Stack_Pop(&nodes);


}

/*requres that cpy has no loops*/
Map* Map_Copy(Map *cpy)
{
	short i;
	Map *ret;

	if(cpy==NULL)
	{
		return NULL;
	}

	ret=malloc(sizeof(Map));
	ret->is_final=cpy->is_final;
	ret->ID=cpy->ID;

	for(i=0;i<256;++i)
	{
		ret->delta[i]=Map_Copy(cpy->delta[i]);
	}
	return ret;
}

struct Map* Map_Check_And_Get(Map *tree, void *str,size_t size)
{
	size_t temp;
	Map_Scour(tree,str,size,&temp,&tree);

	if(temp<size)
	{
		return NULL;	
	}else
	{
		return tree;
	}
}

struct Map* Map_Push_And_Get(struct Map* tree,void *str,size_t size,void *id)
{
	size_t temp;
	Map_Scour(tree,str,size,&temp,&tree);	

	if(temp == size)
	{
		if(tree->ID!=NULL)tree->ID=id;
		tree->is_final=1;
		return tree;
	}

	for(temp;temp<size;++temp)
	{
		Map_Init(
			tree=
			tree->delta[((unsigned char*)str)[temp]]=
			malloc(sizeof(Map))
			);
	}

	tree->ID=id;
	tree->is_final=1;
	return tree;
}

void* Map_Check_And_Push(struct Map *tree,void *str,size_t size,void *id)
{
	size_t temp;
	Map_Scour(tree,str,size,&temp,&tree);	

	if(temp == size)
	{
		if(!tree->is_final)
		{
			tree->ID=id;
			tree->is_final=1;
		}
		return tree->ID;
	}
	for(temp;temp<size;++temp)
	{
		tree=tree->delta[((unsigned char*)str)[temp]]=calloc(1,sizeof(Map));
		/*
		Map_Init(
			tree=tree->delta[((unsigned char*)str)[temp]]=malloc(sizeof(Map))
			);
			*/
	}

	tree->ID=id;
	tree->is_final=1;
	return NULL;
}
/*requires that the map has no loops. does not free the root node*/
/*TODO*/
void Map_Delete_Map(struct Map *tree)
{

}
#endif //#ifndef GMAP