1
00:00:00,000 --> 00:00:07,933
[No Audio]

2
00:00:07,934 --> 00:00:09,900
In the last tutorial, we started with the

3
00:00:09,901 --> 00:00:12,233
implementation of the solution, and this is

4
00:00:12,234 --> 00:00:15,000
where we left the code. We were looking at

5
00:00:15,001 --> 00:00:17,400
the implementation of the move_to_tail function.

6
00:00:17,533 --> 00:00:19,000
So let's start coding it.

7
00:00:19,800 --> 00:00:22,700
We will start by declaring the move_to_tail function.

8
00:00:22,701 --> 00:00:26,733
[No Audio]

9
00:00:26,734 --> 00:00:28,800
The input will be a mutable reference to the

10
00:00:28,801 --> 00:00:31,400
list itself, and a reference to the Node that

11
00:00:31,401 --> 00:00:34,533
we want to move to the tail. Next, we will

12
00:00:34,534 --> 00:00:36,833
grab the information of the Next and Previous

13
00:00:36,834 --> 00:00:40,333
Nodes of the given Node. We would also want

14
00:00:40,334 --> 00:00:42,933
to own these Nodes. To grab the previous Node

15
00:00:42,934 --> 00:00:44,833
information, we will call the borrow function

16
00:00:44,900 --> 00:00:47,900
on Node to borrow it, and we'll access its

17
00:00:47,901 --> 00:00:50,200
previous field which contains the previous

18
00:00:50,201 --> 00:00:52,800
Node information. Next, we will use the

19
00:00:52,801 --> 00:00:55,800
as_ref function for grabbing the

20
00:00:55,801 --> 00:00:58,133
contents of the Node, that is being the

21
00:00:58,134 --> 00:01:01,400
option. This will give us the previous Node

22
00:01:02,000 --> 00:01:04,700
which will not map to the clone copy of the cell.

23
00:01:04,701 --> 00:01:10,300
[No Audio]

24
00:01:10,301 --> 00:01:12,900
This means now that, we now own the previous

25
00:01:12,901 --> 00:01:15,300
Node, and therefore, we can change its

26
00:01:15,301 --> 00:01:18,733
contents. In the same way, we will also grab

27
00:01:18,734 --> 00:01:20,300
the next Node information.

28
00:01:20,301 --> 00:01:26,900
[No Audio]

29
00:01:26,901 --> 00:01:28,833
The previous now contains the previous of the

30
00:01:28,834 --> 00:01:31,700
Node, which corresponds to the item purchased,

31
00:01:31,733 --> 00:01:35,200
and the next contains the next Node. There

32
00:01:35,201 --> 00:01:37,300
can be now four possibilities for the

33
00:01:37,301 --> 00:01:39,400
previous and next. To check for these

34
00:01:39,401 --> 00:01:41,600
possibilities we will use a match on the

35
00:01:41,601 --> 00:01:44,300
previous and next. The first possibility will

36
00:01:44,301 --> 00:01:46,200
be that the previous and next are both None.

37
00:01:46,201 --> 00:01:53,133
[No Audio]

38
00:01:53,134 --> 00:01:55,233
This can only happen if the Node under

39
00:01:55,234 --> 00:01:57,800
investigation is the only Node in the list.

40
00:01:58,533 --> 00:02:01,233
In this case, we do not need to do anything, so

41
00:02:01,234 --> 00:02:04,800
we will keep right side body of the arm empty.

42
00:02:04,801 --> 00:02:10,733
[No Audio]

43
00:02:10,734 --> 00:02:12,933
The second case is that, there is some

44
00:02:12,934 --> 00:02:15,300
previous, but there is nothing in the next.

45
00:02:15,600 --> 00:02:17,733
This will happen when the Node is already at

46
00:02:17,734 --> 00:02:20,100
the tail, because the next of the tail

47
00:02:20,101 --> 00:02:23,733
is always empty. This again means that we do

48
00:02:23,734 --> 00:02:25,800
not need to do anything, because the Node is

49
00:02:25,801 --> 00:02:28,333
already at the tail. So we will keep the

50
00:02:28,334 --> 00:02:31,100
right side of the of the arm empty.

51
00:02:31,101 --> 00:02:32,900
[No Audio]

52
00:02:32,901 --> 00:02:36,233
The next case will be when there is nothing in

53
00:02:36,234 --> 00:02:38,633
the previous, but there is some Node in the next.

54
00:02:38,700 --> 00:02:40,700
This means that the Node we

55
00:02:40,701 --> 00:02:43,601
want to move is at the head of the list, since

56
00:02:43,602 --> 00:02:45,866
the head has None in the previous pointer,

57
00:02:45,867 --> 00:02:47,466
and the next is Some Node.

58
00:02:47,800 --> 00:02:49,233
Let us visually see how

59
00:02:49,234 --> 00:02:51,633
we will move the head to the tail. Consider

60
00:02:51,634 --> 00:02:54,533
this list, where the Node with a value of

61
00:02:54,534 --> 00:02:56,200
3 is at the head of the list,

62
00:02:56,201 --> 00:02:59,400
which we intend to move to the end of the list.

63
00:02:59,800 --> 00:03:01,700
So first we will determine the next and the

64
00:03:01,701 --> 00:03:04,300
previous nodes with respect, with respect to

65
00:03:04,301 --> 00:03:06,333
the Node, which is the Head node in this case.

66
00:03:07,400 --> 00:03:09,600
Next we will update the head information for

67
00:03:09,601 --> 00:03:12,300
the whole list. So we will take out the

68
00:03:12,301 --> 00:03:14,833
previous head from the list, we will update

69
00:03:14,834 --> 00:03:16,966
its next pointer to that of None.

70
00:03:16,967 --> 00:03:19,000
[No Audio]

71
00:03:19,001 --> 00:03:20,633
We will also update the previous

72
00:03:20,634 --> 00:03:22,381
of the next Node as None,

73
00:03:22,400 --> 00:03:24,800
because it is going to be the new head of the

74
00:03:24,801 --> 00:03:27,300
list, and the previous of head is always None.

75
00:03:27,500 --> 00:03:29,833
Finally, we will update the head to that of

76
00:03:29,834 --> 00:03:32,700
the next Node. The red colors in the slide

77
00:03:32,701 --> 00:03:35,500
shows the necessary updates that we need to make.

78
00:03:35,501 --> 00:03:37,800
[No Audio]

79
00:03:37,801 --> 00:03:39,900
Next, we will move the Node that we

80
00:03:39,901 --> 00:03:42,700
have just taken out to the end of the list.

81
00:03:42,900 --> 00:03:45,900
So, let us now see what updations we will

82
00:03:45,901 --> 00:03:49,133
need to make in this regards. We will first

83
00:03:49,134 --> 00:03:51,033
update the next of the prev_tail to that

84
00:03:51,034 --> 00:03:53,600
of the Node shown in the red color. Following

85
00:03:53,601 --> 00:03:55,600
this, we will set the previous pointer of the

86
00:03:55,601 --> 00:03:57,800
Node to that of the prev_tail, and finally

87
00:03:57,801 --> 00:03:59,700
we will update the Tail of the list to that

88
00:03:59,701 --> 00:04:02,800
of the Node, let us now see the implementation.

89
00:04:04,300 --> 00:04:05,733
We will first update the next

90
00:04:05,734 --> 00:04:08,733
of the Nodes. So for that we will borrow it

91
00:04:08,734 --> 00:04:11,100
mutably by calling the borrow_mut

92
00:04:11,101 --> 00:04:12,633
function on the Node, and will update

93
00:04:12,634 --> 00:04:14,333
it's next to that of None.

94
00:04:14,334 --> 00:04:21,200
[No Audio]

95
00:04:21,201 --> 00:04:23,233
Following this, we will update the previous

96
00:04:23,234 --> 00:04:26,100
smart pointer of the next Node to that of None also.

97
00:04:26,101 --> 00:04:29,933
[No Audio]

98
00:04:29,934 --> 00:04:32,800
Finally, we will update the head, so that it

99
00:04:32,801 --> 00:04:34,800
points to the next by using the clone.

100
00:04:35,133 --> 00:04:37,500
Please note that the scope of the next variable is

101
00:04:37,501 --> 00:04:39,933
limited to the scope of this match, and it

102
00:04:39,934 --> 00:04:43,000
will not exist when the function ends. This

103
00:04:43,001 --> 00:04:45,400
does not mean that the head will be a

104
00:04:45,401 --> 00:04:47,401
dangling pointer when the function ends,

105
00:04:47,402 --> 00:04:50,333
because using the clone makes sure that it

106
00:04:50,334 --> 00:04:54,133
owns the data, because it creates a shared ownership.

107
00:04:54,600 --> 00:04:56,500
If you still feel uncomfortable,

108
00:04:56,800 --> 00:04:59,133
then I would suggest you again look at the

109
00:04:59,134 --> 00:05:01,700
details in the section of smart pointers.

110
00:05:02,800 --> 00:05:05,300
Next, we will make the necessary updates to the

111
00:05:05,301 --> 00:05:07,733
tail of the list. First, we will create a

112
00:05:07,734 --> 00:05:11,000
pointer to the tail. We want to have a

113
00:05:11,001 --> 00:05:13,133
reference to the tail Node, therefore we will

114
00:05:13,134 --> 00:05:16,733
use the as_ref function on the self.tail,

115
00:05:16,734 --> 00:05:18,133
and then we'll unwrap it.

116
00:05:18,134 --> 00:05:22,600
[No Audio]

117
00:05:22,601 --> 00:05:25,133
Next, we will update the next pointer of the previous

118
00:05:25,134 --> 00:05:26,400
tail to that of Node.

119
00:05:26,401 --> 00:05:33,000
[No Audio]

120
00:05:33,001 --> 00:05:35,500
We will next, set the previous of the Node to

121
00:05:35,501 --> 00:05:37,400
that of the prev_tail.

122
00:05:37,401 --> 00:05:43,400
[No Audio]

123
00:05:43,401 --> 00:05:45,900
Finally, we will update the tail to that of

124
00:05:45,901 --> 00:05:47,233
the Node itself.

125
00:05:47,234 --> 00:05:54,500
[No Audio]

126
00:05:54,501 --> 00:05:57,033
The last case will be when there is some

127
00:05:57,034 --> 00:06:00,300
previous and some next Node. This means that

128
00:06:00,301 --> 00:06:03,033
the Node we want to move to the end is in the

129
00:06:03,034 --> 00:06:05,600
middle of the list. Let us visually see what

130
00:06:05,601 --> 00:06:07,500
updation will be required in this case.

131
00:06:07,800 --> 00:06:09,400
First, we will determine the Next and

132
00:06:09,401 --> 00:06:11,300
Previous Nodes with respect to the Node that

133
00:06:11,301 --> 00:06:14,100
we wish to move to the end. Next, we will

134
00:06:14,101 --> 00:06:16,900
take it out from the middle, and we'll set the

135
00:06:16,901 --> 00:06:19,800
pointers of the previous and next, so that the

136
00:06:19,801 --> 00:06:23,100
list becomes connected again. To make the

137
00:06:23,101 --> 00:06:25,200
connections, we will first set the next of

138
00:06:25,201 --> 00:06:27,233
the previous Node to that of the next Node.

139
00:06:27,833 --> 00:06:29,833
Then we will set the previous of the next

140
00:06:29,834 --> 00:06:32,700
Node to that of the previous Node.  Moreover,

141
00:06:32,701 --> 00:06:35,233
we will also set the next of the Node to None,

142
00:06:35,600 --> 00:06:38,833
since it is going to be added at the end, and

143
00:06:38,834 --> 00:06:41,933
we know that the next of the tail is None.

144
00:06:43,000 --> 00:06:45,600
We will next, put the Node at the end and we'll set

145
00:06:45,601 --> 00:06:48,200
the pointers accordingly. The next of the

146
00:06:48,201 --> 00:06:50,800
prev_tail will become the Node itself, the

147
00:06:50,801 --> 00:06:53,600
Node previous, the Node's previous will be the

148
00:06:53,601 --> 00:06:56,133
prev_tail, and finally the new

149
00:06:56,134 --> 00:06:59,100
tail will be the Node itself. Let us look at

150
00:06:59,101 --> 00:07:01,100
the implementation of the same in code.

151
00:07:01,101 --> 00:07:03,000
[No Audio]

152
00:07:03,001 --> 00:07:05,233
We will first set the next of the Node to that

153
00:07:05,339 --> 00:07:09,139
of None. Following this, we will set the next

154
00:07:09,140 --> 00:07:11,200
of the previous Node to that of the next Node.

155
00:07:11,201 --> 00:07:18,100
[No Audio]

156
00:07:18,101 --> 00:07:19,600
The previous of the next Node will

157
00:07:19,601 --> 00:07:20,700
become the previous Node.

158
00:07:20,701 --> 00:07:28,933
[No Audio]

159
00:07:28,934 --> 00:07:31,233
Next, we will have a reference to the prev_tail.

160
00:07:31,234 --> 00:07:39,933
[No Audio]

161
00:07:39,934 --> 00:07:43,300
The prev_tail next will become the Node.

162
00:07:43,301 --> 00:07:50,800
[No Audio]

163
00:07:50,801 --> 00:07:53,133
The previous of the Node will be the prev_tail.

164
00:07:53,134 --> 00:07:58,900
[No Audio]

165
00:07:58,901 --> 00:08:01,600
And finally, we will update the tail to that of the Node.

166
00:08:01,601 --> 00:08:07,433
[No Audio]

167
00:08:07,434 --> 00:08:08,900
Okay done.

168
00:08:08,901 --> 00:08:10,900
Now, let us call it from the purchased

169
00:08:10,901 --> 00:08:13,400
function. We were here in the purchase

170
00:08:13,401 --> 00:08:16,300
function, where we looked for a prod_id

171
00:08:16,301 --> 00:08:17,733
in the HashMap, and if there is

172
00:08:17,734 --> 00:08:19,833
some already existing entry, then we will

173
00:08:19,834 --> 00:08:21,900
obtain the corresponding Node from the list,

174
00:08:21,901 --> 00:08:23,700
and then we will move it to the end.

175
00:08:24,033 --> 00:08:26,300
To move the Node to the end, we will simply call the

176
00:08:26,301 --> 00:08:28,400
move_to_tail function,

177
00:08:28,800 --> 00:08:31,200
that we just wrote with the Node as an input.

178
00:08:32,400 --> 00:08:34,900
If the Node is not already in the HashMap,

179
00:08:34,901 --> 00:08:38,433
then we will check first, if the list has some

180
00:08:38,434 --> 00:08:40,700
space for adding the new product or not.

181
00:08:41,600 --> 00:08:44,400
If the list has no space, then we will remove the

182
00:08:44,401 --> 00:08:47,633
head from the list, and will then proceed with

183
00:08:47,634 --> 00:08:49,900
inserting the new element at the tail.

184
00:08:49,901 --> 00:08:52,533
[No Audio]

185
00:08:52,534 --> 00:08:55,300
So let us add a condition to check if the list has

186
00:08:55,301 --> 00:08:57,900
some space or not. Please note that I am

187
00:08:57,901 --> 00:09:00,100
intentionally writing the code as greater

188
00:09:00,101 --> 00:09:03,000
than or equal to and not equal to, and the

189
00:09:03,001 --> 00:09:05,100
reason will become clear to us in a moment.

190
00:09:06,833 --> 00:09:09,300
I would like to remove the head, and we'll store

191
00:09:09,301 --> 00:09:10,433
it in a variable.

192
00:09:10,434 --> 00:09:22,333
[No Audio]

193
00:09:22,334 --> 00:09:24,600
Next, I will remove the prod_id

194
00:09:24,601 --> 00:09:26,333
that is associated with the Node from the

195
00:09:26,334 --> 00:09:28,000
HashMap by calling the remove

196
00:09:28,001 --> 00:09:29,133
function on the HashMap.

197
00:09:29,134 --> 00:09:34,833
[No Audio]

198
00:09:34,834 --> 00:09:37,300
The remove function expects a reference, so

199
00:09:37,301 --> 00:09:40,733
therefore we provided a reference. Next,

200
00:09:40,734 --> 00:09:43,200
if the list is not at the full capacity, then

201
00:09:43,201 --> 00:09:45,533
we will simply add the prod_id at the end

202
00:09:45,534 --> 00:09:47,700
of the list using the push_back

203
00:09:47,701 --> 00:09:51,000
function of the list, and we will store the

204
00:09:51,001 --> 00:09:53,433
newly created Node in the variable of Node.

205
00:09:53,434 --> 00:10:00,800
[No Audio]

206
00:10:00,801 --> 00:10:03,900
Next, we will update update the map also, so

207
00:10:03,901 --> 00:10:06,700
that it contains an entry for the prod_id,

208
00:10:06,701 --> 00:10:08,200
and the Node is the value part.

209
00:10:08,201 --> 00:10:15,533
[No Audio]

210
00:10:15,534 --> 00:10:17,500
Finally, we will update the size.

211
00:10:17,501 --> 00:10:23,100
[No Audio]

212
00:10:23,101 --> 00:10:25,133
Since we are updating the size at the end of

213
00:10:25,134 --> 00:10:27,633
the function, therefore we use the condition

214
00:10:27,634 --> 00:10:30,000
of greater than or equal to at the start of

215
00:10:30,001 --> 00:10:33,000
the code to check if the list is at capacity or not.

216
00:10:33,533 --> 00:10:35,633
If we were updating the size at the

217
00:10:35,634 --> 00:10:37,800
start before inserting the Node, then we would

218
00:10:37,801 --> 00:10:39,800
be using the condition of equality.

219
00:10:40,933 --> 00:10:43,500
Finally, I will I will add and declare a print

220
00:10:43,501 --> 00:10:45,900
function for printing the list of items.

221
00:10:45,901 --> 00:10:51,800
[No Audio]

222
00:10:51,801 --> 00:10:54,133
The input to the function will be a reference to self.

223
00:10:54,166 --> 00:11:00,800
[No Audio]

224
00:11:00,801 --> 00:11:02,400
We will first define a variable called

225
00:11:02,401 --> 00:11:04,600
traversal which will be pointing towards the

226
00:11:04,601 --> 00:11:05,800
head of the list.

227
00:11:05,833 --> 00:11:13,700
[No Audio]

228
00:11:13,701 --> 00:11:16,300
Next, we will iterate until the traversal

229
00:11:16,301 --> 00:11:18,300
becomes empty, and during each iteration we

230
00:11:18,301 --> 00:11:20,333
will update the traversal to that of the next,

231
00:11:20,334 --> 00:11:21,600
of the next Node.

232
00:11:23,800 --> 00:11:25,900
I will create a while loop for iterating.

233
00:11:27,033 --> 00:11:28,600
Inside the loop, I will create

234
00:11:28,601 --> 00:11:31,100
a variable called temp which will contain a

235
00:11:31,101 --> 00:11:32,200
clone of the traversal.

236
00:11:32,201 --> 00:11:37,900
[No Audio]

237
00:11:37,901 --> 00:11:40,100
Then I will print the prod_id

238
00:11:40,101 --> 00:11:42,400
associated with the temp, which is the current

239
00:11:42,401 --> 00:11:44,100
Node in our traversal of the list.

240
00:11:44,101 --> 00:11:50,700
[No Audio]

241
00:11:50,701 --> 00:11:52,900
Finally, I will update the traversal to that

242
00:11:52,901 --> 00:11:54,700
of the next Node in the list.

243
00:11:54,701 --> 00:12:01,733
[No Audio]

244
00:12:01,734 --> 00:12:03,533
Outside the while, I will add an extra

245
00:12:03,534 --> 00:12:06,200
println statement, so that each time the

246
00:12:06,201 --> 00:12:08,600
list is being displayed on a separate line.

247
00:12:08,601 --> 00:12:18,800
[No Audio]

248
00:12:18,801 --> 00:12:21,033
Now let us test the code in the main, I will

249
00:12:21,034 --> 00:12:23,633
first create a new MRP_item

250
00:12:23,634 --> 00:12:26,900
instance, and it will have a capacity of size 3.

251
00:12:27,833 --> 00:12:29,533
Let us add an item to the list by

252
00:12:29,534 --> 00:12:31,433
calling the purchase function and display the

253
00:12:31,434 --> 00:12:32,700
list in cargo run.

254
00:12:32,701 --> 00:12:42,600
[No Audio]

255
00:12:42,601 --> 00:12:44,800
Let us add a couple of more items to the list

256
00:12:44,801 --> 00:12:45,900
and cargo run again.

257
00:12:45,901 --> 00:12:52,733
[No Audio]

258
00:12:52,734 --> 00:12:55,333
You may note that, the newly purchased items

259
00:12:55,334 --> 00:12:57,533
are being added at the end of the list. Let

260
00:12:57,534 --> 00:13:00,000
us now purchase one more item, and print and

261
00:13:00,001 --> 00:13:01,633
cargo run again.

262
00:13:01,634 --> 00:13:10,833
[No Audio]

263
00:13:10,834 --> 00:13:13,100
The newly purchased item has been added at

264
00:13:13,101 --> 00:13:15,100
the end of the list, and the least recently

265
00:13:15,101 --> 00:13:17,600
purchased item which was at the beginning has

266
00:13:17,601 --> 00:13:20,100
been removed, because the list reached to its

267
00:13:20,101 --> 00:13:22,800
capacity. You can test with different inputs

268
00:13:22,801 --> 00:13:25,000
and see the results for yourselves. That

269
00:13:25,001 --> 00:13:27,000
brings us to the end of this tutorial. I hope

270
00:13:27,001 --> 00:13:28,800
you would have enjoyed coding with me this

271
00:13:28,801 --> 00:13:31,533
problem. The takeaways is that the HashMaps

272
00:13:31,600 --> 00:13:33,533
are quite handy for quick searching through

273
00:13:33,534 --> 00:13:36,033
items in the list. Do can make again for more

274
00:13:36,100 --> 00:13:38,700
and until then happy Rust programming

275
00:13:38,701 --> 00:13:45,033
[No Audio]