1
00:00:06,690 --> 00:00:10,890
And this lecture, we're going to implement a few different methods.

2
00:00:11,700 --> 00:00:16,020
The first method we are going to implement is going to be search.

3
00:00:16,740 --> 00:00:25,380
So since we created our iterator, we could very easily use it to search for the value that we want

4
00:00:25,380 --> 00:00:28,260
to see if it is in our tree or not.

5
00:00:28,590 --> 00:00:39,660
But I'm going to take a different approach and not use our iterator for searching our tree if you want.

6
00:00:39,660 --> 00:00:46,620
It would be good practice for you to implement another search method that does use our iterator.

7
00:00:47,160 --> 00:00:48,220
But you don't have to.

8
00:00:48,240 --> 00:00:50,340
But again, it will be good practice.

9
00:00:50,850 --> 00:00:58,440
So what we're going to do is we're going to create our search function as a method and it's going to

10
00:00:58,470 --> 00:01:02,300
need our value passed in.

11
00:01:02,520 --> 00:01:06,240
And what we want to do is we're going to return a Boolean if it exists or not.

12
00:01:08,710 --> 00:01:17,410
So what we want to do is we want to use our compare and ordering

13
00:01:19,990 --> 00:01:23,520
in order to kind of navigate through our tree.

14
00:01:23,530 --> 00:01:26,170
So up here we'll bring ordering into scope.

15
00:01:26,170 --> 00:01:29,260
We'll say compare and ordering.

16
00:01:31,360 --> 00:01:42,880
And now back in our search method, we can say match and self value and we are going to say some key.

17
00:01:44,500 --> 00:01:52,120
And then inside this code block, we are going to match on our compete our key and compare it to our

18
00:01:52,120 --> 00:01:52,720
value.

19
00:01:54,160 --> 00:01:58,240
So there are three things that we can have here equal greater and less.

20
00:01:58,240 --> 00:02:02,050
So we'll start with the easy one, which is equal.

21
00:02:03,850 --> 00:02:10,540
So this means that our key equals the value, therefore it is in the tree.

22
00:02:10,540 --> 00:02:12,220
So key equals value.

23
00:02:12,220 --> 00:02:14,740
So if it's in the tree, then we want to return true.

24
00:02:16,240 --> 00:02:19,600
Otherwise we can have greater.

25
00:02:20,890 --> 00:02:31,150
And this means that our key is greater than the value, which means that we need to go to the left because

26
00:02:31,150 --> 00:02:36,460
we're looking for a key that is now going to be less than the value.

27
00:02:36,460 --> 00:02:45,370
So we will say self left and we will say some node and we will say node dot search.

28
00:02:45,370 --> 00:02:55,270
So call our search again on our value and then if nothing comes back, then we know the value is not

29
00:02:55,270 --> 00:02:55,750
in the tree.

30
00:02:55,750 --> 00:02:57,250
So we return false.

31
00:02:58,630 --> 00:03:02,410
So now and I see I have a typo here, so we will go ahead and fix that.

32
00:03:02,410 --> 00:03:11,500
So now we have ordering and our last one is less than so in here this means our key is less than the

33
00:03:11,500 --> 00:03:12,130
value.

34
00:03:12,310 --> 00:03:14,680
And so this means we need to go to the right.

35
00:03:14,680 --> 00:03:19,990
So we will say self dot right and it'll be the same as above.

36
00:03:19,990 --> 00:03:25,120
So we'll have node, node dot search on our value.

37
00:03:25,150 --> 00:03:28,900
Otherwise, if nothing comes back, then we know it's not in the tree.

38
00:03:28,900 --> 00:03:31,480
So we return false.

39
00:03:33,150 --> 00:03:42,180
And then to do our catch all, we return false here as well.

40
00:03:42,300 --> 00:03:44,670
To close off this match statement.

41
00:03:45,570 --> 00:03:48,770
So let's just make sure that the syntax is right.

42
00:03:48,780 --> 00:03:55,450
So let's do a cargo build and there we go, do another cargo build.

43
00:03:55,470 --> 00:03:57,330
All right, so syntax is right here.

44
00:03:57,330 --> 00:04:00,660
So search seems to be working fine.

45
00:04:00,660 --> 00:04:03,000
So we'll leave it as is for now.

46
00:04:03,750 --> 00:04:09,390
And then we'll implement our test cases for all of the methods we're creating at the end of this lecture.

47
00:04:10,710 --> 00:04:15,630
So now that we have search done, let's implement a method called minimum.

48
00:04:15,630 --> 00:04:21,600
And minimum is going to return the smallest value in the tree.

49
00:04:22,680 --> 00:04:33,990
So we will say pub effin minimum and we will need ourself and we have option with a reference to T.

50
00:04:34,950 --> 00:04:39,780
So in here we have our match self left because we want the minimum.

51
00:04:39,780 --> 00:04:45,300
So we know that we have to go to the left and we will say some node.

52
00:04:47,720 --> 00:05:01,670
No dot minimum because we want to get the minimum note and we will say none if nothing is less than

53
00:05:01,670 --> 00:05:06,770
self dot value dot as ref.

54
00:05:07,250 --> 00:05:13,220
So once we get the minimum value, then nothing will be less than our self left.

55
00:05:13,220 --> 00:05:17,960
So we want to return our value as a reference.

56
00:05:18,590 --> 00:05:27,890
So if we have a minimum, naturally we need to have a maximum and this is going to return the maximum

57
00:05:28,520 --> 00:05:30,740
value in the tree.

58
00:05:32,750 --> 00:05:38,960
So we have self, we're going to return our option.

59
00:05:39,140 --> 00:05:42,410
They reference to our value and it'll be the same thing.

60
00:05:42,410 --> 00:05:42,890
Match.

61
00:05:42,890 --> 00:05:47,570
And so start right some node

62
00:05:50,210 --> 00:05:54,770
and we want node dot maximum.

63
00:05:54,770 --> 00:06:03,680
Once we get the maximum we will have none and we want to return self value as ref.

64
00:06:05,750 --> 00:06:06,080
All right.

65
00:06:06,080 --> 00:06:08,020
So we have minimum and maximum.

66
00:06:08,030 --> 00:06:11,030
Again, we will test these once.

67
00:06:13,280 --> 00:06:17,720
Once we are done implementing our our methods just to ensure that they work.

68
00:06:18,290 --> 00:06:28,790
So the next method we want to implement is called floor and floor is going to return the largest value

69
00:06:28,790 --> 00:06:36,320
in the tree, smaller than the value parameter that we pass in.

70
00:06:37,190 --> 00:06:43,310
So we will say pub effin floor and we know that we need ourself.

71
00:06:43,310 --> 00:06:55,730
But this one is going to take a reference to a TX type called value and we will say option and we will

72
00:06:55,730 --> 00:06:57,260
turn a reference to our value.

73
00:06:58,070 --> 00:07:02,210
So inside a floor we need to do a couple of things.

74
00:07:03,560 --> 00:07:12,170
The first thing is we need to match on our value and then for some key.

75
00:07:19,100 --> 00:07:24,190
Add in a code block and then for some key we want to match in on key compare.

76
00:07:24,200 --> 00:07:31,520
So this should look kind of familiar since we just did this in our search method and now we want to

77
00:07:31,520 --> 00:07:36,140
do ordering greater so again.

78
00:07:37,860 --> 00:07:42,170
This means that the key is greater than the value.

79
00:07:42,180 --> 00:07:43,590
So we're going to we're on the right.

80
00:07:43,590 --> 00:07:46,980
So we're going to go to the right match itself, Right?

81
00:07:49,020 --> 00:07:56,070
Or excuse me, we want to go to the left, because in this case we want the largest value in the tree,

82
00:07:56,070 --> 00:08:00,090
smaller than so we want to go to the left.

83
00:08:01,440 --> 00:08:14,880
So now that we're going to the left, we will say some node node dot floor on the value and then none,

84
00:08:16,860 --> 00:08:17,360
none.

85
00:08:17,400 --> 00:08:26,520
So if there is no value that is less than this value, then we return none.

86
00:08:28,560 --> 00:08:30,270
So now we have greater done.

87
00:08:31,350 --> 00:08:36,630
So now we want to do our less than so we have ordering less.

88
00:08:38,730 --> 00:08:43,860
And so this means that the key is less than the value, which means in this case we want to go to the

89
00:08:43,860 --> 00:08:51,720
right because we're looking for that specific value.

90
00:08:51,720 --> 00:08:55,230
So we say some node.

91
00:08:57,760 --> 00:09:04,480
And then inside of this code block, we're going to say let Val equals node .4. value.

92
00:09:05,260 --> 00:09:12,760
So now we're trying to get us that value that we're looking for and we're going to match on that.

93
00:09:12,760 --> 00:09:16,970
Value at that value exists and is valid.

94
00:09:17,060 --> 00:09:19,260
We don't want to do anything with that value.

95
00:09:19,270 --> 00:09:22,390
We just want to return that value.

96
00:09:22,750 --> 00:09:28,870
Otherwise, if that value does not exist, then we just want to return our key.

97
00:09:32,860 --> 00:09:39,130
And so now all we're trying to do is exhaust all of our match statements.

98
00:09:39,130 --> 00:09:43,420
So this none is matching this match statement.

99
00:09:43,420 --> 00:09:44,950
So we will say none.

100
00:09:46,000 --> 00:09:47,050
Some key.

101
00:09:50,080 --> 00:09:52,210
So now we're at our last.

102
00:09:52,690 --> 00:09:57,520
So instead of if it's not greater than or less than, we can be equal.

103
00:09:57,940 --> 00:09:59,590
So now we're trying to handle that.

104
00:09:59,680 --> 00:10:03,550
Which in that case, if it's equal, then we would just return some key

105
00:10:05,890 --> 00:10:07,030
otherwise.

106
00:10:08,440 --> 00:10:13,630
Now, if nothing works, then we just return none.

107
00:10:14,230 --> 00:10:17,830
And this looks pretty good.

108
00:10:17,920 --> 00:10:20,650
So what are we doing here again?

109
00:10:20,680 --> 00:10:24,130
We're matching on our value with some key.

110
00:10:24,400 --> 00:10:27,790
We're comparing that key to the value.

111
00:10:29,620 --> 00:10:34,290
If it is greater than then, we want to go to the left to try to get that value.

112
00:10:34,300 --> 00:10:35,320
That is.

113
00:10:37,270 --> 00:10:40,540
The greatest value, but less than our value.

114
00:10:40,720 --> 00:10:41,200
Right.

115
00:10:41,200 --> 00:10:49,120
So if if we pass in a six year, then it would be great if we had a value of like five, right?

116
00:10:49,120 --> 00:10:54,700
Because it's the largest value we can have in the tree, smaller than six.

117
00:10:55,150 --> 00:11:01,150
So that is what we're trying to do here and our floor.

118
00:11:01,240 --> 00:11:03,610
So if we're greater, then we go to the left.

119
00:11:03,880 --> 00:11:07,660
If we are less than then we need to go to the right, right.

120
00:11:07,660 --> 00:11:11,800
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

121
00:11:11,800 --> 00:11:13,090
that five on the right.

122
00:11:13,450 --> 00:11:16,660
And then here we're trying to get that value.

123
00:11:16,930 --> 00:11:18,730
We want to match that value.

124
00:11:19,000 --> 00:11:24,370
If that value is valid and is is good, then we return that value.

125
00:11:24,370 --> 00:11:26,680
Otherwise we just return our key.

126
00:11:29,500 --> 00:11:34,960
And then we just start exhausting the rest of our match statements because Rust wants our match statements

127
00:11:34,960 --> 00:11:36,040
to be exhaustive.

128
00:11:36,220 --> 00:11:38,570
So all of this looks pretty good.

129
00:11:38,590 --> 00:11:43,300
Obviously, we need to test it out to ensure that it looks good.

130
00:11:46,900 --> 00:11:49,930
So here we're going to do our test, our searching.

131
00:11:52,570 --> 00:11:59,140
And we're going to say let free equals creator tree.

132
00:12:01,720 --> 00:12:17,830
So we want to assert if our tree search contains a reference to five and then we'll do a couple more

133
00:12:17,830 --> 00:12:19,000
just to make sure.

134
00:12:20,830 --> 00:12:24,370
So we want to see if five exist, if seven exist.

135
00:12:25,450 --> 00:12:27,280
We'll see if 15 exist.

136
00:12:27,280 --> 00:12:29,880
And then we'll see if two exists.

137
00:12:29,890 --> 00:12:35,190
And since we expect two to not exist, we expect false to be returned here.

138
00:12:35,200 --> 00:12:37,990
So we want to make sure that that is what we're checking for.

139
00:12:41,470 --> 00:12:49,680
Our next test case is going to be testing our max admin methods.

140
00:12:50,050 --> 00:12:53,020
So we will let tree equals.

141
00:12:55,080 --> 00:12:56,330
Create a tree.

142
00:12:56,340 --> 00:13:04,230
And then in here we will say assert equals and we want tree dot maximum.

143
00:13:05,910 --> 00:13:20,130
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.

144
00:13:20,130 --> 00:13:24,660
So we will change this to minimum and our minimum value will be zero.

145
00:13:26,220 --> 00:13:35,970
And lastly, we have testing our floor, so test loop floor.

146
00:13:37,440 --> 00:13:49,380
And then here we will say let tree equals create tree and then we will say assert equals.

147
00:13:51,600 --> 00:13:52,490
The reference.

148
00:13:52,500 --> 00:13:55,190
3.4.

149
00:13:57,560 --> 00:14:01,520
We will pass in reference to 42.

150
00:14:04,050 --> 00:14:06,510
Unwrap the value that is returned.

151
00:14:06,510 --> 00:14:17,520
And if we pass in 42 and our tree, then we expect 34 to be returned.

152
00:14:17,520 --> 00:14:19,850
So that is why we put 34 here.

153
00:14:19,860 --> 00:14:23,670
So notice the value that we pass in does not have to be in the tree.

154
00:14:24,300 --> 00:14:33,870
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

155
00:14:33,870 --> 00:14:34,560
to verify.

156
00:14:34,560 --> 00:14:39,000
So we'll do floor and we'll do 30

157
00:14:41,220 --> 00:14:42,240
and 30.

158
00:14:42,240 --> 00:14:46,260
We would expect 27 to be returned.

159
00:14:46,260 --> 00:14:52,560
So now if we run our test cases, we see that everything passes successfully.

160
00:14:52,560 --> 00:14:57,000
So it looks like all of our methods are running correctly, which is great.

161
00:14:57,900 --> 00:15:01,110
But now I have a little assignment for you.

162
00:15:01,410 --> 00:15:04,260
So there is like maximum minimum.

163
00:15:04,260 --> 00:15:10,800
There is a counterpart for sealing or for flooring excuse me, and it is called seal.

164
00:15:11,130 --> 00:15:19,140
So we want to test floor and seal here, test seal method.

165
00:15:20,370 --> 00:15:32,400
And for us to test seal method, we will say assert equals and we will de reference our tree dot seal

166
00:15:32,400 --> 00:15:33,360
excuse me.

167
00:15:34,350 --> 00:15:40,590
And here we will pass in six, we will unwrap it.

168
00:15:40,590 --> 00:15:46,950
And if passing in six, we expect seven to be returned.

169
00:15:47,280 --> 00:15:47,610
Right.

170
00:15:47,610 --> 00:15:57,030
So what is seal sealing is going to return the smallest value in the tree greater than the value we

171
00:15:57,030 --> 00:15:57,720
pass in.

172
00:15:57,720 --> 00:15:59,730
So we're passing in six.

173
00:15:59,730 --> 00:16:03,630
So if we look at our tree, what is the smallest value?

174
00:16:03,720 --> 00:16:07,080
Greater than six it will be seven.

175
00:16:07,080 --> 00:16:09,330
So that is why we want seven returned.

176
00:16:09,720 --> 00:16:21,780
So if we did another value, we'll say we'll put in 40, then we would expect 43 to be returned here.

177
00:16:22,800 --> 00:16:32,400
So to set this up, because I want you to take this time after this lecture to try to implement in the

178
00:16:32,400 --> 00:16:33,360
SEAL method.

179
00:16:33,510 --> 00:16:46,140
So we will have our self, we will pass in our value and we are going to return just like this.

180
00:16:46,650 --> 00:16:58,350
So for the assignment I want you to implement in the SEAL method and just as a hint, it will be similar

181
00:16:58,350 --> 00:17:01,950
to floor with minor tweaks to it.

182
00:17:01,950 --> 00:17:10,320
So think about what we did for Max and men and how similar they were and try to implement in the SEAL

183
00:17:10,320 --> 00:17:10,920
method.

184
00:17:11,520 --> 00:17:19,110
We will go over my solution to this assignment in the next lecture and if you have any questions, please

185
00:17:19,110 --> 00:17:24,570
feel free to ask them in the Q&A section and I will get back to you as quickly as I can.