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
14typedef 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
25char *
26strip (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
51void
52insert (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
93void
94populate_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
123int
124find_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
141void
142print_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
158int
159main (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