1 //===-- dictionary.c ---------------------------------------------*- C -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===---------------------------------------------------------------------===//
9 #include <ctype.h>
10 #include <stdio.h>
11 #include <stdlib.h>
12 #include <string.h>
13 
14 typedef struct tree_node {
15   const char *word;
16   struct tree_node *left;
17   struct tree_node *right;
18 } tree_node;
19 
20 /* Given a char*, returns a substring that starts at the first
21    alphabet character and ends at the last alphabet character, i.e. it
22    strips off beginning or ending quotes, punctuation, etc. */
23 
24 char *strip(char **word) {
25   char *start = *word;
26   int len = strlen(start);
27   char *end = start + len - 1;
28 
29   while ((start < end) && (!isalpha(start[0])))
30     start++;
31 
32   while ((end > start) && (!isalpha(end[0])))
33     end--;
34 
35   if (start > end)
36     return NULL;
37 
38   end[1] = '\0';
39   *word = start;
40 
41   return start;
42 }
43 
44 /* Given a binary search tree (sorted alphabetically by the word at
45    each node), and a new word, inserts the word at the appropriate
46    place in the tree.  */
47 
48 void insert(tree_node *root, char *word) {
49   if (root == NULL)
50     return;
51 
52   int compare_value = strcmp(word, root->word);
53 
54   if (compare_value == 0)
55     return;
56 
57   if (compare_value < 0) {
58     if (root->left != NULL)
59       insert(root->left, word);
60     else {
61       tree_node *new_node = (tree_node *)malloc(sizeof(tree_node));
62       new_node->word = strdup(word);
63       new_node->left = NULL;
64       new_node->right = NULL;
65       root->left = new_node;
66     }
67   } else {
68     if (root->right != NULL)
69       insert(root->right, word);
70     else {
71       tree_node *new_node = (tree_node *)malloc(sizeof(tree_node));
72       new_node->word = strdup(word);
73       new_node->left = NULL;
74       new_node->right = NULL;
75       root->right = new_node;
76     }
77   }
78 }
79 
80 /* Read in a text file and storea all the words from the file in a
81    binary search tree.  */
82 
83 void populate_dictionary(tree_node **dictionary, char *filename) {
84   FILE *in_file;
85   char word[1024];
86 
87   in_file = fopen(filename, "r");
88   if (in_file) {
89     while (fscanf(in_file, "%s", word) == 1) {
90       char *new_word = (strdup(word));
91       new_word = strip(&new_word);
92       if (*dictionary == NULL) {
93         tree_node *new_node = (tree_node *)malloc(sizeof(tree_node));
94         new_node->word = new_word;
95         new_node->left = NULL;
96         new_node->right = NULL;
97         *dictionary = new_node;
98       } else
99         insert(*dictionary, new_word);
100     }
101   }
102 }
103 
104 /* Given a binary search tree and a word, search for the word
105    in the binary search tree.  */
106 
107 int find_word(tree_node *dictionary, char *word) {
108   if (!word || !dictionary)
109     return 0;
110 
111   int compare_value = strcmp(word, dictionary->word);
112 
113   if (compare_value == 0)
114     return 1;
115   else if (compare_value < 0)
116     return find_word(dictionary->left, word);
117   else
118     return find_word(dictionary->right, word);
119 }
120 
121 /* Print out the words in the binary search tree, in sorted order.  */
122 
123 void print_tree(tree_node *dictionary) {
124   if (!dictionary)
125     return;
126 
127   if (dictionary->left)
128     print_tree(dictionary->left);
129 
130   printf("%s\n", dictionary->word);
131 
132   if (dictionary->right)
133     print_tree(dictionary->right);
134 }
135 
136 int main(int argc, char **argv) {
137   tree_node *dictionary = NULL;
138   char buffer[1024];
139   char *filename;
140   int done = 0;
141 
142   if (argc == 2)
143     filename = argv[1];
144 
145   if (!filename)
146     return -1;
147 
148   populate_dictionary(&dictionary, filename);
149   fprintf(stdout, "Dictionary loaded.\nEnter search word: ");
150   while (!done && fgets(buffer, sizeof(buffer), stdin)) {
151     char *word = buffer;
152     int len = strlen(word);
153     int i;
154 
155     for (i = 0; i < len; ++i)
156       word[i] = tolower(word[i]);
157 
158     if ((len > 0) && (word[len - 1] == '\n')) {
159       word[len - 1] = '\0';
160       len = len - 1;
161     }
162 
163     if (find_word(dictionary, word))
164       fprintf(stdout, "Yes!\n");
165     else
166       fprintf(stdout, "No!\n");
167 
168     fprintf(stdout, "Enter search word: ");
169   }
170 
171   fprintf(stdout, "\n");
172   return 0;
173 }
174