#include <stdlib.h>

typedef struct TrieNode
{
	char c;
	int filled;
	struct TrieNode *left;
	struct TrieNode *right;
}trie;

static trie* create_node(char c);

trie* trie_initialize()
{
	trie* head;

	if((head = (trie*)malloc(sizeof(*head))) == NULL)
		return NULL;

	head->c = '\0';
	head->filled = 0;
	head->left = head;
	head->right = NULL;

	return head;
}

int trie_lookup(trie *head, char *word)
{
	trie *lp, *rp;

	/* search in trie proceeds by compairing a character of the argument to the character in the tree,
		and following right link until finding a match; then the left link is taken and we treat the
		next character of the argument in the same way */

	for(lp = head->right; lp != NULL; lp = lp->left)		/* moving down a level */
	{
		for(rp = lp; rp != NULL; rp = rp->right)			/* moving towards right */
		{
			if(rp->c == *word)
				break;
		}

		/* no match */
		if(rp == NULL)
			return 0;

		/* if the characters in the word are exhausted, then it's a match only if the left link
			is NULL or the word is filled (it reresent a complete word */
		if(*(++word) == '\0')
		{
			if(rp->left == NULL || rp->filled)
				return 1;

			return 0;
		}
		lp = rp;
	}

	/* trie ends and the word still have character(s) left*/
	return 0;
}

/* return 0 if word already present; return 1 if bind succesful; otherwise on error return -1*/
int trie_bind(trie *head, char *word)
{
	trie *lp, *rp, *plp;

	if(word == NULL)
		return -1;

	/* search the word */
	for(lp = head, plp = head; lp != NULL; plp = lp, lp = lp->left)		/* moving down a level */
	{
		trie *prp;

		for(rp = lp, prp = lp; rp != NULL; prp = rp, rp = rp->right)			/* moving towards right */
		{
			if(rp->c == *word)
				break;
		}

		/* no match, bind the word */
		if(rp == NULL)
		{
			prp->right = create_node(*word);

			if(prp->right == NULL)
				return -1;

			if(*(++word) == '\0')
				return 1;

			plp = prp->right;
			break;
		}

		if(*(++word) == '\0')
		{
			if(rp->left == NULL)
				return 0;

			if(rp->filled)
				return 0;
			else
			{
				rp->filled = 1;
				return 1;
			}
		}
		lp = rp;
	}

	/* trie ends and the word still have character(s) left */

	do
	{
		plp->left = create_node(*word);

		if(plp->left == NULL)
			return -1;

		plp = plp->left;
	}
	while(*(++word) != '\0');

	return 1;
}

static trie* create_node(char c)
{
	trie* p;

	if((p = (trie*)malloc(sizeof(*p))) == NULL)
		return NULL;

	p->c = c;
	p->filled = 0;
	p->left = NULL;
	p->right = NULL;

	return p;
}