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