>> SPEAKER 1: 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 star
Children bracket alphabet.
So first thing you might be wondering, why is alphabet hash 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.
>> OK, now, remember how a Trie actually works.
Let's say we're indexing the word cats, then from the root of our 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 would be index two.
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 index that 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 if the word catastrophe is in our dictionary, but
the word cat is not?
So in looking to see if the word cat is in our dictionary, we're going to
successfully look through the indices C-A-T and reach a 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 indicate whether this particular location actually
indicates a word.
>> All right, so now that we know what a 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 dictionary and this is going to be the dictionary
that we want to load.
So first thing we're going to do is open up that dictionary for reading.
We have to make sure we didn't fail, so if the dictionary was not
successfully opened, it will return No, 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 star.
It's the top of our Trie that we're going to be iterating through.
So first thing 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's actually
successful.
If this returned null, then we need to close our dictionary
file and return False.
So assuming the allocation was successful, we're going to use a node
star Cursor to iterate through our Trie.
So our root's never going to change, but we're going to use Cursor to
actually go from node to node.
>> All right, so in this For loop, we are reading through the dictionary file,
and we're using at fgetc.
So 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, so 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 equal to alphabet minus 1, which will be the index 26.
Else, if it was not an apostrophe, then we're going to set the index
equal to c minus a.
So remember back from previous p sets, c minus 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 would 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 array, 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 do here.
So we're going to, again, use the Calloc function so that we don't have
to zero out all of 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 to 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.
>> OK, so 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 word.
>> All right, 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 equals 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 the dictionary into our Trie.
>> All right, 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 we going to 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 passed, 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 bracket i is an
apostrophe, then we want to use index alphabet minus 1 because we determined
that is where we're going to store apostrophes.
>> Else we're going to use tolower 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 lowercase 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
to update our cursor to point to that particular node at that index.
>> So we keep doing that throughout the entire word.
Assuming we never hit null, that means we were able to get through the entire
world and find a node in our Trie, but we're not quite done yet.
We don't want to just return True.
We want to return cursor error word since, remember again, if cat is not
in our dictionary and catastrophe is, then we will successfully 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.
>> All right, 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 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 going to 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 ourself.
So this will 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 [INAUDIBLE].