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