[MUSIC PLAYING] 

ROB BOWDEN: Hi. I'm Rob. And let's this solution out. So here we're going to implement a general table. We see that the struct node of our table is going to look like this. So it's going to have a char word array of size LENGTH + 1. Don't forget the + 1, since the maximum word in the dictionary is 45 characters. And then we're going to need one extra character for the backslash zero. 

And then our hashtable in each bucket is going to store a linked list of nodes. We are not doing linear probing here. And so in order to link to the next element in the bucket, we need a struct node* next. OK. So that's what a node looks like. 

Now here is the declaration of our hashtable. It's going to have 16,834 buckets. But that number doesn't really matter. And finally, we're going to have the global variable hashtable size, which is going to start off as zero. And it's going to keep track of how many words are in our dictionary. 

So let's take a look at load. Notice that load, it returns a bool. You return true if it was successfully loaded, and false otherwise. And it takes a const char* dictionary, which is the dictionary that we want to open. So that's the first thing we're going to do. 

We're going to fopen the dictionary for reading. And we're going to have to make sure that it succeeded. So if it returned NULL, then we did not successfully open the dictionary. And we need to return false. But assuming that it did successfully open, then we want to read the dictionary. So keep looping until we find some reason to break out of this loop, which we'll see. So keep looping. 

And now we're going to malloc a single node. And of course we need to air check again. So if mallocing did not succeed, then we want to unload any node that we happened to malloc before, close the dictionary and return false. But ignoring that, assuming we succeeded, then we want to use fscanf to read a single word from our dictionary into our node. So remember that entry>word is the char word buffer of size LENGHTH + 1 that we're going to store the word in. 

So fscanf is going to return 1, as long as it was able to successfully read a word from the file. If either an error happens, or we reach the end of the file, it will not return 1. In which case it does not return 1, we're finally going to break out of this while loop. So we see that once we have successfully read a word into entry>word, then we're going to that word using our hash function. 

Let's take a look at the hash function. So you don't really need to understand this. And actually we just pulled this hash function from the internet. The only thing you need to recognize is that this takes a const char* word. So it's taking a string as input, and returning an unsigned int as output. So that's all a hash function is, is it takes in an input and gives you an index into the hashtable. 

Notice that we're moding by NUM_BUCKETS, so that value returned actually is an index into the hashtable and doesn't index beyond the bounds of the array. So given that function, we're going to hash the word that we read the dictionary. And then we're going to use that hash to insert the entry into the hashtable. 

Now hashtable hash is the current linked list in the table. And it's very possible that it's just NULL. We want to insert our entry at the beginning of this linked list. And so we're going to have our current entry point to what the hashtable currently points to. And then we're going to store, in the hashtable at the hash, the current entry. So these two lines successfully insert the entry at the beginning of the linked list at that index in the hashtable. 

Once we're done with that, we know that we found another word in the dictionary, and we increment again. So we keep doing that until fscanf finally returned something non-1 at which point remember that we need to free entry. So up here we malloced an entry. And we tried to read something from the dictionary. And we did not successfully read something from the dictionary, in which case we need to free the entry that we never actually put into the hashtable, and finally break. 

Once we break out we need to see, well, did we break out because there was an error reading from the file? Or did we break out because we reached the end of the file? If there was an error, then we want to return false. Because load did not succeed. And in the process we want to unload all the words that we read in, and close the dictionary file. 

Assuming we did succeed, then we just still need to close the dictionary file, and finally return true since we successfully loaded the dictionary. And that's it for load. So now check, given a loaded hashtable, is going to look like this. So check, it returns a bool, which is going to indicate whether the passed in char* word, whether the passed in string is in our dictionary. So if it is in the dictionary, if it is in our hashtable, we will return true. And if it's not, we will return false. 

Given this passed in word, we're going to hash the word. Now an important thing to recognize is that in load we knew that all of the words we're going to be lower case. But here we're not so sure. If we take a look at our hash function, our hash function actually is lower casing each character of the word. So regardless of the capitalization of word, our hash function is the return the same index for whatever the capitalization is, as it would have returned for a completely lowercase version of the word. Alright. That's our index is into the hashtable for this word. 

Now this for loop is going to iterate over the linked list that was at that index. So notice we are initializing entry to point to that index. We're going to continue while entry != NULL. And remember that updating the pointer in our linked list entry=entry>next. So have our current entry point to the next item in the linked list. 

So for each entry in the linked list, we're going to use strcasecmp. It's not strcomp. Because once again, we want to do things case insensitively. So we use strcasecmp to compare the word that was passed through this function against the word that is in this entry. If it returns zero, that means there was a match, in which case we want to return true. We successfully found the word in our hashtable. 

If there was not a match, then we're going to loop again and look at the next entry. And we'll continue looping while there are entries in this linked list. What happens if we break out of this for loop? That means we did not find an entry that matched this word, in which case we return false to indicate that our hashtable did not contain this word. And that's a check. 

So let's take a look at size. Now size is going to be pretty simple. Since remember in load, for each word we found, we incremented a global variable hashtable size. So the size function is just going to return global variable. And that's it. 

Now finally, we need to unload the dictionary once everything's done. So how are we going to do that? Right here we're looping over all buckets of our table. So there are NUM_BUCKETS buckets. And for each linked list in our hashtable, we're going to loop over the entirety of the linked list, freeing each element. 

Now we need to be careful. So here we have a temporary variable that's storing the pointer to the next element in the linked list. And then we're going to free the current element. We need to be sure we do this since we can't just free the current element and then try to access the next pointer, since once we've freed it, the memory becomes invalid. 

So we need to keep around a pointer to the next element, then we can free the current element, and then we can update our current element to point to the next element. We'll loop while there are elements in this linked list. We'll do that for all linked lists in the hashtable. And once we're done with that, we've completely unloaded the hashtable, and we're done. So it's impossible for unload to ever return false. And when we're done, we just return true. 

Let's give this solution a try. So let's take a look at what our struct node will look like. Here we see we're going to have a bool word and a struct node* children bracket ALPHABET. So the first thing you might be wondering, why is ALPHABET ed defined as 27? Well, remember that we're going to need to be handling the apostrophe. So that's going to be somewhat of a special case throughout this program. 

Now remember how a trie actually works. Let's say we're indexing the word "cats." Then from the root of trie, we're going to look at the children array, and we're going to look at the index that corresponds to the letter C. So that will be indexed 2. So given that, that will give us a new node. And then we'll work from that node. 

So given that node, we're once again going to look at the children array. And we're going to look at index zero to correspond to the A in cat. So then we're going to go to that node, and given that node we're going to look at the end it's a corresponds to T. And moving on to that node, finally, we have completely looked through our word "cat." And now bool word is supposed to indicate whether this given word is actually a word. 

So why do we need that special case? Well what of the word "catastrophe" is in our dictionary, but the word "cat" is not? So and looking to see if the word "cat" is in our dictionary, we're going to successfully look through the indices C-A-T in region node. But that's only because catastrophe happened to create nodes on the way from C-A-T, all the way to the end of the word. So bool word is used to indicate whether this particular location actually indicates a word. 

All right. So now that we know what it trie is going to look like, let's look at the load function. So load is going to return a bool for whether we successfully or unsuccessfully loaded the dictionary. And this is going to be the dictionary that we want to load. 

So first thing we're to do is open up that dictionary for reading. And we have to make sure we didn't fail. So if the dictionary was not successfully opened, it will return null, in which case we're going to return false. But assuming that it successfully opened, then we can actually read through the dictionary. 

So first thing we're going to want to do is we have this global variable root. Now root is going to be a node*. It's the top of our trie that we're going to be iterating through. So the first thing that we're going to want to do is allocate memory for our root. Notice that we're using the calloc function, which is basically the same as the malloc function, except it's guaranteed to return something that is completely zeroed out. So if we used malloc, we would need to go through all of the pointers in our node, and make sure that they're all null. So calloc will do that for us. 

Now just like malloc, we need to make sure that the allocation was actually successful. If this returned null, then we need to close or dictionary file and return false. So assuming that allocation was successful, we're going to use a node* cursor to iterate through our trie. So our roots never going to change, but we're going to use cursor to actually go from node to node. 

So in this for loop we are reading through the dictionary file. And we're using fgetc. Fgetc is going to grab a single character from the file. We're going to continue grabbing characters while we do not reach the end of the file. 

There are two cases we need to handle. The first, if the character was not a new line. So we know if it was a new line, then we're about to move on to a new word. But assuming it was not a new line, then here we want to figure out the index we're going to index into in the children array that we looked at before. 

So, like I said before, we need to special case the apostrophe. Notice we're using the ternary operator here. So we're going to read this as, if the character we read in was an apostrophe, then we're going to set index= "ALPHABET"-1, which will be the index 26. 

Else, if it was not an apostrophe, there we're going to set the index equal to c - a. So remember back from previously p-sets, c - a is going to give us the alphabetical position of C. So if C is the letter A, this will give us index zero. For the letter B, it will give us the index 1, and so on. 

So this gives us the index into the children array that we want. Now if this index is currently null in the children, that means that a node does not currently exist from that path. So we need to allocate a node for that path. That's what we'll do here. 

So we're going to again use the calloc function, so that we don't have to zero out all the pointers. And we again need to check that calloc did not fail. If calloc did fail, then we need to unload everything, close our dictionary, and return false. So assuming that it did not fail, then this will create a new child for us. And then we will go to that child. Our cursor will iterate down to that child. 

Now if this was not null to begin with, then the cursor can just iterate down to that child without actually having to allocate anything. This is the case where we first happened allocate the word "cat." And that means when we go to allocate "catastrophe," we don't need to create nodes for C-A-T again. They already exist. 

What is this else? This is the condition where c was backslash n, where c was a new line. This means that we have successfully completed a word. Now what do we want to do when we successfully completed a word? We're going to use this word field inside of our struct node. We want to set that to true. So that indicates that this node indicates a successful word, an actual word. 

Now set that to true. We want to reset our cursor to point to the beginning of the trie again. And finally, increment our dictionary size, since we found another work. So we're going to keep doing that, reading in character by character, constructing new nodes in our trie and for each word in the dictionary, until we finally reach C != EOF, in which case we break out of the file. 

Now there are two cases under which we might have hit EOF. The first is if there was an error reading from the file. So if there was an error, we need to do the typical. Unload everything, close the file, return false. Assuming there was not an error, that just means we actually hit the end of the file, in which case, we close the file and return true since we successfully loaded dictionary into our trie. 

So now let's check out check. Looking at the check function, we see that check is going to return a bool. It returns true if this word that it's being passed is in our trie. It returns false otherwise. So how are you determine whether this word is in our trie? 

We see here that, just like before, we're going to use cursor to iterate through our trie. Now here we're going to iterate over our entire word. So iterating over the word we are past, we're going to determine the index into the children array that corresponds to word bracket I. So this is going to look exactly like load, where if word[i] is an apostrophe, then we want to use index "ALPHABET" - 1. Because we determined that that is where we're going to store apostrophes. 

Else we're going to use two lower word bracket I. So remember that word can have arbitrary capitalization. And so we want to make sure that we're using a lowercase version of things. And then subtract from that 'a' to once again give us the alphabetical position of that character. So that's going to be our index into the children array. 

And now if that index into the children array is null, that means we can no longer continue iterating down our trie. If that's the case, this word cannot possibly be in our trie. Since if it were, that would mean there would be a path down to that word. And you would never encounter null. So encountering null, we return false. The word is not in the dictionary. If it were not null, then we're going to continue iterating. 

So we're going out there cursor to point to that particular node at that index. We keep doing that throughout the entire word, assuming we never hit null. That means we were able to get through the entire word and find a node in our try. But we're not quite done yet. 

We don't want to just return true. We want to return cursor>word. Since remember again, is "cat" is not in our dictionary, and "catastrophe" is, then we will successfully we get through the word "cat." But cursor word will be false and not true. So we return cursor word to indicate whether this node is actually a word. And that's it for check. 

So let's check out size. So size is going to be pretty easy since, remember in load, we're incrementing dictionary size for each word that we encounter. So size is just going to return dictionary size. And that's it. 

So lastly we have unload. So unload, we're going to use a recursive function to actually do all of the work for us. So our function is going to be called on unloader. What is unloader going to do? We see here that unloader is going to iterate over all of the children at this particular node. And if the child node is not null, then we're going to unload the child node. 

So this is you recursively unload all of our children. Once we're sure that all of our children have been unloaded, then we can free ourselves, so unload ourselves. This will work recursively unload the entire trie. And then once that's done, we can just return true. Unload cannot fail. We're just freeing things. So once we're done freeing everything, return true. And that's it. My name is Rob. And this was speller. 

[MUSIC PLAYING]