1. // Implements a dictionary's functionality
2.  
3. #include <stdbool.h>
4. #include <string.h>
5. #include <stdio.h>
6. #include <cs50.h>
7. #include <stdlib.h>
8. #include <strings.h>
9. #include <ctype.h>
10.  
11.  
12. #include "dictionary.h"
13.  
14. // define hashtable size of 2 ^ 16
15. #define HASHTABLE_SIZE 65536
16.  
17. // declare a counter variable to count number of words in the dictionary
18. int wordcount = 0;
19.  
20. // Represents a node in a hash table
21. typedef struct node
22. {
23.     char word[LENGTH + 1];
24.     struct node *next;
25. }
26. node;
27.  
28. // Number of buckets in hash table
29. const unsigned int N = 65536;
30.  
31. // declare the hashtable
32. node *hashtable[HASHTABLE_SIZE];
33.  
34. // Hash table
35. node *table[HASHTABLE_SIZE];
36.  
37. // Returns true if word is in dictionary else false
38. bool check(const char *word)
39. {
40.     // TODO
41.     // declare lowercase word
42.     char lcase_word[LENGTH + 1];
43.    
44.     // convert words to lowercase
45.     for (int i = 0; i < LENGTH; i++)
46.     {
47.         lcase_word[i] = tolower(word[i]);
48.     }
49.    
50.     // hash word to obtain hash value
51.     int index = hash(lcase_word);
52.    
53.     // set up cursor variable to traverse linked list
54.     node *cursor = hashtable[index];
55.    
56.     // have cursor traverse linked listed until end
57.     while (cursor != NULL)
58.     {
59.         // check words in node to find if word if target word is there
60.         if (strcasecmp (word, cursor->word) == 0)
61.         {
62.             // return true if target word is there
63.             return true;
64.         }
65.        
66.         cursor = cursor->next;
67.     }
68.     return false;
69. }
70.  
71.  
72. // Hashes word to a number
73. unsigned int hash(const char *word)
74. {
75.     // TODO
76.     // hash function from: https://www.reddit.com/r/cs50/comments/1x6vc8/pset6_trie_vs_hashtable/cf9nlkn/
77.     unsigned int hash = 0;
78.     for (int i = 0, n = strlen(word); i < n; i++)
79.        {
80.          hash = (hash << 2) ^ word[i];
81.        }
82.     return hash % HASHTABLE_SIZE;
83. }
84.  
85. // Loads dictionary into memory, returning true if successful else false
86. bool load(const char *dictionary)
87. {
88.     // TODO
89.     // open dictionary file
90.     FILE *dictptr = fopen(dictionary, "r");
91.     if (dictptr == NULL)
92.     {
93.         return false;
94.     }
95.  
96.     // declare variable to read words into
97.     char word[LENGTH + 1];
98.    
99.     while (fscanf(dictptr, "%s", word) != EOF)
100.     {
101.         // allocate enough memory to store a node
102.         node *newnode = malloc(sizeof(node));
103.    
104.         // check if malloc was successful
105.         if (newnode == NULL)
106.         {
107.             return false;
108.         }
109.         // copy words into node
110.         strcpy (newnode->word, word);
111.         newnode->next = NULL;
112.        
113.         // hash the word: insert into hashtable
114.         int index = hash(newnode->word);
115.        
116.         // if bucket is empty
117.         if (hashtable[index] == NULL)
118.         {
119.             hashtable[index] = newnode;
120.             newnode->next = NULL;
121.         }
122.        
123.         else
124.         {
125.         // if bucket is not empty
126.             newnode->next = hashtable[index];
127.             hashtable[index] = newnode;
128.         }
129.        
130.         wordcount++;
131.     }
132.     fclose(dictptr);
133.     return true;
134. }
135.  
136. // Returns number of words in dictionary if loaded else 0 if not yet loaded
137. unsigned int size(void)
138. {
139.     // TODO
140.     // from load function word added from dictionary were counted as each was added
141.     return wordcount;
142. }
143.  
144. // Unloads dictionary from memory, returning true if successful else false
145. bool unload(void)
146. {
147.     // TODO
148.     // iterate over all the  nodes in the linked list
149.     for (int i = 0; i < HASHTABLE_SIZE; i++)
150.     {
151.      // initialise a tmp variable and a cursor varible
152.      // point them to beginning of the linked list
153.         node *tmp = hashtable[i];
154.         node *cursor = hashtable[i];
155.            
156.         while (hashtable[i] != NULL)
157.         {
158.             if (cursor != NULL)
159.             {
160.                 tmp = cursor;
161.                 cursor = cursor->next;
162.                 free(tmp);
163.             }
164.         }
165.         free(cursor);
166.     }
167.     return true;
168. }
169.