trie.c

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define STR_HELPER(x) #x
#define STR(x) STR_HELPER(x)

#define TRIE_INIT_SIZE 100
#define TRIE_ALPHABET_SIZE 26
#define FIRST_LETTER 'a'
#define MAX_WORD_LENGTH 100
#define TRUE 1
#define FALSE 0

typedef struct node{
	int is_word;
	struct node * next[TRIE_ALPHABET_SIZE];
}Trie;

Trie * _traverse_tree(Trie * trie, char * word, int add_nodes, Trie ** prev_root, int * prev_index){
	Trie * root = trie;
	Trie * local_prev_root = trie;
	int index;

	while(*word){
		if(!isalpha(*word)){
			word++;
			continue;
		}

		int letter_index = tolower((int)*word);
		index = letter_index - FIRST_LETTER;

		Trie * next_root = root->next[index];
		if(next_root == NULL){
			if(add_nodes)
				next_root = root->next[index] = (Trie *)calloc(sizeof(Trie), 1);
			else
				return NULL;
		}

		local_prev_root = root;
		root = next_root;
		word++;
	}

	if(prev_index != NULL)
		*prev_index = index;
	if(prev_root != NULL)
		*prev_root = local_prev_root;

	return root;
}

void add_word(Trie * trie, char * word){
	Trie * root = _traverse_tree(trie, word, TRUE, NULL, NULL);
	root->is_word = TRUE;
}

void remove_word(Trie * trie, char * word){
	int prev_index;
	Trie * prev_node;
	Trie * root = _traverse_tree(trie, word, TRUE, &prev_node, &prev_index);

	if(root != NULL){
		root->is_word = FALSE;

		int i;
		for(i = 0; i < 26; i++){
			if(root->next[i] != NULL)
				return;
		}

		prev_node->next[prev_index] = NULL;
		free(root);
	}
}

int is_word(Trie * trie, char * word){
	Trie * root = _traverse_tree(trie, word, TRUE, NULL, NULL);
	return root != NULL && root->is_word;
}

void load_words_from_file(Trie * trie, char * word_file){
	FILE * file = fopen(word_file, "r");
	while(!feof(file)){
		char word_buffer[MAX_WORD_LENGTH + 1];
		fscanf(file, "%" STR(MAX_WORD_LENGTH) "s", word_buffer);

		add_word(trie, word_buffer);
	}
}

int main(int argc, char * argv[]){
	(void)argc;
	(void)argv;

	Trie * trie = (Trie *)calloc(sizeof(Trie), 1);
	load_words_from_file(trie, "/usr/share/dict/words");

	while(!feof(stdin)){
		char word_buffer[MAX_WORD_LENGTH + 1];

		int selection;
		printf("Enter 1 to check a word\n");
		printf("Enter 2 to add a word\n");
		printf("Enter 3 to delete a word\n");
		printf("Select: ");
		scanf("%d", &selection);
		if(selection < 1 || selection > 3){
			printf("Invalid choice\n\n");
			continue;
		}

		printf("Enter a word: ");
		scanf("%" STR(MAX_WORD_LENGTH) "s", word_buffer);

		char * negate;
		switch(selection){
			case 1:
				negate = (is_word(trie, word_buffer)) ? "" : "not ";
				printf("%s is %sin the dictionary\n", word_buffer, negate);
				break;
			case 2:
				add_word(trie, word_buffer);
				break;
			case 3:
				remove_word(trie, word_buffer);
				break;

		}
		printf("\n");
	}

}