And this lecture, we're going to implement a few different methods.
The first method we are going to implement is going to be search.
So since we created our iterator, we could very easily use it to search for the value that we want
to see if it is in our tree or not.
But I'm going to take a different approach and not use our iterator for searching our tree if you want.
It would be good practice for you to implement another search method that does use our iterator.
But you don't have to.
But again, it will be good practice.
So what we're going to do is we're going to create our search function as a method and it's going to
need our value passed in.
And what we want to do is we're going to return a Boolean if it exists or not.
So what we want to do is we want to use our compare and ordering
in order to kind of navigate through our tree.
So up here we'll bring ordering into scope.
We'll say compare and ordering.
And now back in our search method, we can say match and self value and we are going to say some key.
And then inside this code block, we are going to match on our compete our key and compare it to our
value.
So there are three things that we can have here equal greater and less.
So we'll start with the easy one, which is equal.
So this means that our key equals the value, therefore it is in the tree.
So key equals value.
So if it's in the tree, then we want to return true.
Otherwise we can have greater.
And this means that our key is greater than the value, which means that we need to go to the left because
we're looking for a key that is now going to be less than the value.
So we will say self left and we will say some node and we will say node dot search.
So call our search again on our value and then if nothing comes back, then we know the value is not
in the tree.
So we return false.
So now and I see I have a typo here, so we will go ahead and fix that.
So now we have ordering and our last one is less than so in here this means our key is less than the
value.
And so this means we need to go to the right.
So we will say self dot right and it'll be the same as above.
So we'll have node, node dot search on our value.
Otherwise, if nothing comes back, then we know it's not in the tree.
So we return false.
And then to do our catch all, we return false here as well.
To close off this match statement.
So let's just make sure that the syntax is right.
So let's do a cargo build and there we go, do another cargo build.
All right, so syntax is right here.
So search seems to be working fine.
So we'll leave it as is for now.
And then we'll implement our test cases for all of the methods we're creating at the end of this lecture.
So now that we have search done, let's implement a method called minimum.
And minimum is going to return the smallest value in the tree.
So we will say pub effin minimum and we will need ourself and we have option with a reference to T.
So in here we have our match self left because we want the minimum.
So we know that we have to go to the left and we will say some node.
No dot minimum because we want to get the minimum note and we will say none if nothing is less than
self dot value dot as ref.
So once we get the minimum value, then nothing will be less than our self left.
So we want to return our value as a reference.
So if we have a minimum, naturally we need to have a maximum and this is going to return the maximum
value in the tree.
So we have self, we're going to return our option.
They reference to our value and it'll be the same thing.
Match.
And so start right some node
and we want node dot maximum.
Once we get the maximum we will have none and we want to return self value as ref.
All right.
So we have minimum and maximum.
Again, we will test these once.
Once we are done implementing our our methods just to ensure that they work.
So the next method we want to implement is called floor and floor is going to return the largest value
in the tree, smaller than the value parameter that we pass in.
So we will say pub effin floor and we know that we need ourself.
But this one is going to take a reference to a TX type called value and we will say option and we will
turn a reference to our value.
So inside a floor we need to do a couple of things.
The first thing is we need to match on our value and then for some key.
Add in a code block and then for some key we want to match in on key compare.
So this should look kind of familiar since we just did this in our search method and now we want to
do ordering greater so again.
This means that the key is greater than the value.
So we're going to we're on the right.
So we're going to go to the right match itself, Right?
Or excuse me, we want to go to the left, because in this case we want the largest value in the tree,
smaller than so we want to go to the left.
So now that we're going to the left, we will say some node node dot floor on the value and then none,
none.
So if there is no value that is less than this value, then we return none.
So now we have greater done.
So now we want to do our less than so we have ordering less.
And so this means that the key is less than the value, which means in this case we want to go to the
right because we're looking for that specific value.
So we say some node.
And then inside of this code block, we're going to say let Val equals node .4. value.
So now we're trying to get us that value that we're looking for and we're going to match on that.
Value at that value exists and is valid.
We don't want to do anything with that value.
We just want to return that value.
Otherwise, if that value does not exist, then we just want to return our key.
And so now all we're trying to do is exhaust all of our match statements.
So this none is matching this match statement.
So we will say none.
Some key.
So now we're at our last.
So instead of if it's not greater than or less than, we can be equal.
So now we're trying to handle that.
Which in that case, if it's equal, then we would just return some key
otherwise.
Now, if nothing works, then we just return none.
And this looks pretty good.
So what are we doing here again?
We're matching on our value with some key.
We're comparing that key to the value.
If it is greater than then, we want to go to the left to try to get that value.
That is.
The greatest value, but less than our value.
Right.
So if if we pass in a six year, then it would be great if we had a value of like five, right?
Because it's the largest value we can have in the tree, smaller than six.
So that is what we're trying to do here and our floor.
So if we're greater, then we go to the left.
If we are less than then we need to go to the right, right.
So if we're less than so, if we're four, then we need to go to the right because we want to look for
that five on the right.
And then here we're trying to get that value.
We want to match that value.
If that value is valid and is is good, then we return that value.
Otherwise we just return our key.
And then we just start exhausting the rest of our match statements because Rust wants our match statements
to be exhaustive.
So all of this looks pretty good.
Obviously, we need to test it out to ensure that it looks good.
So here we're going to do our test, our searching.
And we're going to say let free equals creator tree.
So we want to assert if our tree search contains a reference to five and then we'll do a couple more
just to make sure.
So we want to see if five exist, if seven exist.
We'll see if 15 exist.
And then we'll see if two exists.
And since we expect two to not exist, we expect false to be returned here.
So we want to make sure that that is what we're checking for.
Our next test case is going to be testing our max admin methods.
So we will let tree equals.
Create a tree.
And then in here we will say assert equals and we want tree dot maximum.
Unwrap it and we want a 43 and we need to d reference the sky and then we want to do the same for minimum.
So we will change this to minimum and our minimum value will be zero.
And lastly, we have testing our floor, so test loop floor.
And then here we will say let tree equals create tree and then we will say assert equals.
The reference.
3.4.
We will pass in reference to 42.
Unwrap the value that is returned.
And if we pass in 42 and our tree, then we expect 34 to be returned.
So that is why we put 34 here.
So notice the value that we pass in does not have to be in the tree.
So I did 42 to make sure that 34 is returned so we don't have to see if we could do another floor just
to verify.
So we'll do floor and we'll do 30
and 30.
We would expect 27 to be returned.
So now if we run our test cases, we see that everything passes successfully.
So it looks like all of our methods are running correctly, which is great.
But now I have a little assignment for you.
So there is like maximum minimum.
There is a counterpart for sealing or for flooring excuse me, and it is called seal.
So we want to test floor and seal here, test seal method.
And for us to test seal method, we will say assert equals and we will de reference our tree dot seal
excuse me.
And here we will pass in six, we will unwrap it.
And if passing in six, we expect seven to be returned.
Right.
So what is seal sealing is going to return the smallest value in the tree greater than the value we
pass in.
So we're passing in six.
So if we look at our tree, what is the smallest value?
Greater than six it will be seven.
So that is why we want seven returned.
So if we did another value, we'll say we'll put in 40, then we would expect 43 to be returned here.
So to set this up, because I want you to take this time after this lecture to try to implement in the
SEAL method.
So we will have our self, we will pass in our value and we are going to return just like this.
So for the assignment I want you to implement in the SEAL method and just as a hint, it will be similar
to floor with minor tweaks to it.
So think about what we did for Max and men and how similar they were and try to implement in the SEAL
method.
We will go over my solution to this assignment in the next lecture and if you have any questions, please
feel free to ask them in the Q&A section and I will get back to you as quickly as I can.