#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