blob: 260eab486e1be5b051b3c44f0abf29d0c28ba541 [file] [log] [blame]
//===-- dictionary.c ---------------------------------------------*- C -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===---------------------------------------------------------------------===//
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct tree_node {
const char *word;
struct tree_node *left;
struct tree_node *right;
} tree_node;
/* Given a char*, returns a substring that starts at the first
alphabet character and ends at the last alphabet character, i.e. it
strips off beginning or ending quotes, punctuation, etc. */
char *strip(char **word) {
char *start = *word;
int len = strlen(start);
char *end = start + len - 1;
while ((start < end) && (!isalpha(start[0])))
start++;
while ((end > start) && (!isalpha(end[0])))
end--;
if (start > end)
return NULL;
end[1] = '\0';
*word = start;
return start;
}
/* Given a binary search tree (sorted alphabetically by the word at
each node), and a new word, inserts the word at the appropriate
place in the tree. */
void insert(tree_node *root, char *word) {
if (root == NULL)
return;
int compare_value = strcmp(word, root->word);
if (compare_value == 0)
return;
if (compare_value < 0) {
if (root->left != NULL)
insert(root->left, word);
else {
tree_node *new_node = (tree_node *)malloc(sizeof(tree_node));
new_node->word = strdup(word);
new_node->left = NULL;
new_node->right = NULL;
root->left = new_node;
}
} else {
if (root->right != NULL)
insert(root->right, word);
else {
tree_node *new_node = (tree_node *)malloc(sizeof(tree_node));
new_node->word = strdup(word);
new_node->left = NULL;
new_node->right = NULL;
root->right = new_node;
}
}
}
/* Read in a text file and storea all the words from the file in a
binary search tree. */
void populate_dictionary(tree_node **dictionary, char *filename) {
FILE *in_file;
char word[1024];
in_file = fopen(filename, "r");
if (in_file) {
while (fscanf(in_file, "%s", word) == 1) {
char *new_word = (strdup(word));
new_word = strip(&new_word);
if (*dictionary == NULL) {
tree_node *new_node = (tree_node *)malloc(sizeof(tree_node));
new_node->word = new_word;
new_node->left = NULL;
new_node->right = NULL;
*dictionary = new_node;
} else
insert(*dictionary, new_word);
}
}
}
/* Given a binary search tree and a word, search for the word
in the binary search tree. */
int find_word(tree_node *dictionary, char *word) {
if (!word || !dictionary)
return 0;
int compare_value = strcmp(word, dictionary->word);
if (compare_value == 0)
return 1;
else if (compare_value < 0)
return find_word(dictionary->left, word);
else
return find_word(dictionary->right, word);
}
/* Print out the words in the binary search tree, in sorted order. */
void print_tree(tree_node *dictionary) {
if (!dictionary)
return;
if (dictionary->left)
print_tree(dictionary->left);
printf("%s\n", dictionary->word);
if (dictionary->right)
print_tree(dictionary->right);
}
int main(int argc, char **argv) {
tree_node *dictionary = NULL;
char buffer[1024];
char *filename;
int done = 0;
if (argc == 2)
filename = argv[1];
if (!filename)
return -1;
populate_dictionary(&dictionary, filename);
fprintf(stdout, "Dictionary loaded.\nEnter search word: ");
while (!done && fgets(buffer, sizeof(buffer), stdin)) {
char *word = buffer;
int len = strlen(word);
int i;
for (i = 0; i < len; ++i)
word[i] = tolower(word[i]);
if ((len > 0) && (word[len - 1] == '\n')) {
word[len - 1] = '\0';
len = len - 1;
}
if (find_word(dictionary, word))
fprintf(stdout, "Yes!\n");
else
fprintf(stdout, "No!\n");
fprintf(stdout, "Enter search word: ");
}
fprintf(stdout, "\n");
return 0;
}