// C implementation of search and insert operations 
// on Trie 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <stdbool.h> 
#define pi(x)      printf("%s = %d\n", #x, x);
#define pc(x)      printf("%s = %c\n", #x, x);
#define pp(x)      printf("%s = %p\n", #x, x);
#define ps(x)      printf("%s = %s\n", #x, x);
#define pb(x)      printf("%s = %s\n", #x, x==true?"true":"false");
struct regex_string_structure
{
	char * string;
	int index;
	int len;
	int malloced;
};

struct regex_string
{
	char * string;
	int index;
	int len;
	int malloced;
};

#define str_malloc_(y, z) \
	(y).string = malloc(z); \
	memset((y).string, 0, z); \
	(y).malloced = z; \
	(y).len = 0; \
	(y).index = 0; 

#define str_mallocr(y, z) \
	str_malloc_((y), z); \
	
#define str_malloc(y, z) \
	struct regex_string y; \
	str_mallocr((y), z);

#define str_new(str) \
	str_malloc(str, 1) \

#define str_free_(y) \
	memset((y).string, 0, (y).malloced); \
	free((y).string); \
	(y).string = NULL; \
	(y).malloced = 0; \
	(y).len = 0; \
	(y).index = 0; \

#define str_free(y) \
	{ \
		str_free_((y)); \
	}
	
#define str_reset_(str) { \
	str_free_((str)) \
	str_malloc_((str), 1) \
}

#define str_reset(str) { \
	str_reset_((str)) \
}

#define str_realloc(y, z) \
	(y).string = realloc((y).string, z); \
	if ((y).malloced < z) { \
		memset((y).string+(y).malloced, 0, (z)-(y).malloced); \
	} \
	(y).malloced = z;

#define str_insert_char(str, ch) { \
	str_realloc((str), (str).malloced+2); \
	(str).string[(str).index] = ch; \
	(str).index++; \
	(str).string[(str).index] = 0; \
	(str).len = strlen((str).string); \
}

#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0]) 

// Alphabet size (# of symbols) 
#define ALPHABET_SIZE (26) 

// Converts key current character into index 
// use only 'a' through 'z' and lower case 
#define CHAR_TO_INDEX(c) ((int)c - (int)'a') 

// trie node 
struct TrieNode 
{ 
	struct TrieNode *children[ALPHABET_SIZE]; 
	int idx;

	// isEndOfWord is true if the node represents 
	// end of a word 
	bool isEndOfWord; 
}; 

// Returns new trie node (initialized to NULLs) 
struct TrieNode *getNode(int idx) 
{ 
	struct TrieNode *pNode = NULL; 

	pNode = (struct TrieNode *)malloc(sizeof(struct TrieNode)); 

	if (pNode) 
	{ 
		int i; 

		pNode->isEndOfWord = false; 
		pNode->idx = idx;
		for (i = 0; i < ALPHABET_SIZE; i++) 
			pNode->children[i] = NULL; 
	} 

	return pNode; 
} 

// If not present, inserts key into trie 
// If the key is prefix of trie node, just marks leaf node 
void insert(struct TrieNode *root, const char *key, int dest_idx) 
{ 
	int level; 
	int length = strlen(key); 
	int index; 

	struct TrieNode *pCrawl = root; 

	for (level = 0; level < length; level++) 
	{ 
		index = CHAR_TO_INDEX(key[level]); 
		if (!pCrawl->children[index]) 
			pCrawl->children[index] = getNode(dest_idx); 

		else pCrawl->children[index]->idx = dest_idx;

		pCrawl = pCrawl->children[index]; 
	} 

	// mark last node as leaf 
	pCrawl->isEndOfWord = true; 
} 

// Returns true if key presents in trie, else false 
bool search(struct TrieNode *root, const char *key, int idx) 
{ 
	int level; 
	int length = strlen(key); 
	int index; 
	struct TrieNode *pCrawl = root; 
	pi(idx);
	for (level = 0; level < length; level++) 
	{
		index = CHAR_TO_INDEX(key[level]);
		if (!pCrawl->children[index]) {
			index = CHAR_TO_INDEX('x');
			if (!pCrawl->children[index]) return false; 
		}

		pCrawl = pCrawl->children[index]; 
	} 

	pi(pCrawl->idx);
	return (pCrawl != NULL && pCrawl->isEndOfWord && pCrawl->idx == idx); 
} 

// Returns true if key presents in trie, else false 
bool search_segmented(struct TrieNode *root, struct TrieNode *segments, const char *key) 
{ 
	int level; 
	int length = strlen(key); 
	int index; 
	struct TrieNode *pCrawl = root; 
	
	str_new(segment);
	int idx = 0;

	for (level = 0; level < length; level++) 
	{
		str_insert_char(segment, key[level]);
		
		ps(segment.string);
		pb(search(segments, segment.string, idx));
		if (search(segments, segment.string, idx)) {
			str_reset(segment);
			idx++;
		}
		index = CHAR_TO_INDEX(key[level]);

		if (!pCrawl->children[index]) {
			index = CHAR_TO_INDEX('x');
			if (!pCrawl->children[index]) return false; 
		}

		pCrawl = pCrawl->children[index]; 
	} 
	str_free(segment);
	return (pCrawl != NULL && pCrawl->isEndOfWord); 
} 

#define isp(root, segments, c) printf("%s --- %s\n", c, output[search_segmented(root, segments, c)] )

// Driver 
int main() 
{ 
	char output[][32] = {"Not present in trie", "Present in trie"}; 


	struct TrieNode *root = getNode(0); 
	struct TrieNode *segments = getNode(0); 

	// Construct trie 
	insert(segments, "0011", 0);
	insert(segments, "001", 1);
	insert(segments, "0", 2);
	insert(root, "00110010", 0);

	// Search for different keys 
	isp(root, segments, "00110010");
	return 0; 
}