6 files changed, 475 insertions, 0 deletions
diff --git a/src/misc/map.c b/src/misc/map.c
new file mode 100644
index 0000000..cd8272f
--- /dev/null
+++ b/src/misc/map.c
@@ -0,0 +1,285 @@
+#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
diff --git a/src/misc/map.h b/src/misc/map.h
new file mode 100644
index 0000000..ced43a7
--- /dev/null
+++ b/src/misc/map.h
@@ -0,0 +1,41 @@
+#ifndef GMAP_H
+#define GMAP_H GMAP_H
+#include <stdlib.h>
+#include <stdio.h>
+#include <stack.h>
+#include <queue.h>
+#include <assert.h>
+
+typedef struct Map Map;
+
+
+
+/*
+ * 	A looples automata with things attached to the nodes
+ * */
+struct Map
+{
+	char is_final;
+	Map *delta[256];
+	/*ID cannot point to itself ( this is used in the deletion of the map ) */
+	void *ID; 
+};
+
+void Map_Init(Map *tree);
+void Map_Scour(Map *tree,void *str,size_t size,size_t *where,Map **final_node);
+void Map_Push(Map *tree,void *str,size_t size,void *id);
+void* Map_Check(Map *tree, void *str,size_t size);
+struct Map* Map_Check_And_Get(Map *tree, void *str,size_t size);
+void Map_Remove(Map *tree, void *str,size_t size);
+void Map_Map(Map *tree,void (*map)(void*));
+void Map_Map_Extended(Map *tree,void (*map)(void*,void*),void* pass_data);
+
+void Map_Destroy(Map *tree);
+void Map_Delete_Map(struct Map *tree);
+struct Condensed_Map* Map_Condense(Map* tree);
+
+struct Map* Map_Push_And_Get(struct Map* tree,void *str,size_t size,void *id);
+/*returns NULL if id is not taken , returns pointer to taken id otherwise*/
+void* Map_Check_And_Push(struct Map *tree,void *str,size_t size,void *id);
+
+#endif
diff --git a/src/misc/queue.c b/src/misc/queue.c
new file mode 100644
index 0000000..b395acf
--- /dev/null
+++ b/src/misc/queue.c
@@ -0,0 +1,67 @@
+#ifndef GQUEUE_C
+#define GQUEUE_C GQUEUE_C
+#include<queue.h>
+
+
+void Queue_Init(struct Queue *q)
+{
+	q->first=q->last=NULL;
+	q->size=0;
+}
+void Queue_Push(struct Queue *q,void *data)
+{
+	if(q==NULL)return;
+	if(q->first==NULL)
+	{
+		q->first=q->last=malloc(sizeof(struct Queue_Node));	
+
+		q->first->data=data;
+		q->first->prev=NULL;
+
+		++q->size;
+	}else
+	{
+		struct Queue_Node *temp=malloc(sizeof(struct Queue_Node));
+		q->last->prev=temp;
+		temp->data=data;
+		temp->prev=NULL;
+		q->last=temp;
+		++q->size;
+	}
+
+}
+void* Queue_Pop(struct Queue *q)
+{
+	if(q==NULL)return NULL;
+	if(q->size==0)return NULL;
+
+	void *return_value=q->first->data;
+
+	if(q->size==1)
+	{
+		free(q->last);
+		q->first=q->last=NULL;
+		q->size=0;
+	}else
+	{
+		struct Queue_Node *temp_first=q->first;
+		q->first=q->first->prev;
+		free(temp_first);
+		--q->size;
+	}
+	return return_value;
+}
+void Queue_Destroy(struct Queue *q)
+{
+	
+	struct Queue_Node *temp_first;
+	while(q->first!=NULL)
+	{
+		temp_first=q->first;
+		q->first=q->first->prev;
+		free(temp_first->data);
+		free(temp_first);	
+	}	
+
+}
+#endif 
diff --git a/src/misc/queue.h b/src/misc/queue.h
new file mode 100644
index 0000000..651d4b0
--- /dev/null
+++ b/src/misc/queue.h
@@ -0,0 +1,23 @@
+#ifndef GQUEUE_H
+#define GQUEUE_H GQUEUE_H
+#include<stdlib.h>
+
+
+struct Queue_Node
+{
+	void *data;
+	struct Queue_Node *prev;
+};
+
+struct Queue
+{
+	struct Queue_Node *first,*last;	
+	size_t size;
+	
+};
+
+void Queue_Init(struct Queue *q);
+void Queue_Push(struct Queue *q,void *data);
+void* Queue_Pop(struct Queue *q);
+void Queue_Destroy(struct Queue *q);
+#endif
diff --git a/src/misc/stack.c b/src/misc/stack.c
new file mode 100644
index 0000000..272732f
--- /dev/null
+++ b/src/misc/stack.c
@@ -0,0 +1,37 @@
+#ifndef GSTACK_C
+#define GSTACK_C GSTACK_C
+#include "stack.h"
+
+
+
+void Stack_Init(Stack *stack)
+{
+    stack->size=0;
+    stack->first=NULL;
+}
+void Stack_Push(Stack *stack,void* data)
+{
+    struct Stack_Node *temp_node=malloc(sizeof(struct Stack_Node));
+    temp_node->data=data;
+    temp_node->next=stack->first;
+    stack->first=temp_node;
+    ++stack->size;
+}
+void* Stack_Pop(Stack *stack)
+{
+    void* return_value=NULL;
+    if(stack->first!=NULL)
+    {
+        struct Stack_Node *temp_first=stack->first;
+        return_value=stack->first->data;
+
+        --stack->size;
+        stack->first=stack->first->next;
+        free(temp_first);
+    }
+
+    return return_value;
+}
+
+#endif//#ifndef GSTACK_C
+
diff --git a/src/misc/stack.h b/src/misc/stack.h
new file mode 100644
index 0000000..14e557a
--- /dev/null
+++ b/src/misc/stack.h
@@ -0,0 +1,22 @@
+#ifndef GSTACK_H
+#define GSTACK_H GSTACK_H
+#include<stdlib.h>
+typedef struct Stack Stack;
+
+struct Stack_Node
+{
+	struct Stack_Node *next;
+	void *data;
+};
+struct Stack
+{
+	struct Stack_Node *first;
+	size_t size;
+};
+
+void Stack_Init(Stack *stack);
+void Stack_Push(Stack *stack,void* data);
+void* Stack_Pop(Stack *stack);
+
+
+#endif