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

2
00:00:07,601 --> 00:00:10,233
Welcome back again. In this tutorial, we will

3
00:00:10,234 --> 00:00:12,766
be looking at an interesting problem, which

4
00:00:12,767 --> 00:00:14,966
we will be solving using doubly Linked lists

5
00:00:14,967 --> 00:00:18,066
and HashMaps, the scenario goes like this.

6
00:00:18,400 --> 00:00:20,966
A business is interesting in knowing the

7
00:00:20,967 --> 00:00:23,033
products that has been purchased most

8
00:00:23,034 --> 00:00:25,633
recently by a customer, they will use this

9
00:00:25,634 --> 00:00:27,266
information in their promotional and

10
00:00:27,267 --> 00:00:29,966
marketing campaigns. They would like to store

11
00:00:29,967 --> 00:00:32,000
this information in a suitable data structure,

12
00:00:32,001 --> 00:00:34,133
where they can easily determine a list of

13
00:00:34,134 --> 00:00:36,666
some predetermined number of most recently

14
00:00:36,667 --> 00:00:39,300
purchase products. The business is also very

15
00:00:39,301 --> 00:00:41,233
critical about the speed of the retrieved

16
00:00:41,234 --> 00:00:43,933
information from the data structure. Let us

17
00:00:43,934 --> 00:00:45,733
look at the problem in a bit more detail

18
00:00:45,734 --> 00:00:50,266
using slides. Consider this to be the list of

19
00:00:50,267 --> 00:00:52,066
products that are being purchased in the

20
00:00:52,067 --> 00:00:54,400
order given in the list. We would like to

21
00:00:54,401 --> 00:00:56,966
store information about four most recently

22
00:00:56,967 --> 00:01:00,600
purchased items or products. When the item

23
00:01:00,601 --> 00:01:02,566
1 is being purchased, we will store it in

24
00:01:02,567 --> 00:01:05,366
the list. Next item 2 is being purchased,

25
00:01:05,367 --> 00:01:08,333
so we will store 2. In the same way, we have

26
00:01:08,334 --> 00:01:10,433
the information about the next two items

27
00:01:10,434 --> 00:01:13,600
which are being purchased. At this stage, the

28
00:01:13,601 --> 00:01:16,433
list is at full capacity, and most recently

29
00:01:16,434 --> 00:01:18,800
item that is being purchased is at the end of

30
00:01:18,801 --> 00:01:21,666
the list. While the least recently purchased

31
00:01:21,667 --> 00:01:24,233
or the oldest purchased item is at the

32
00:01:24,234 --> 00:01:27,000
beginning of the list. Now when the customer

33
00:01:27,001 --> 00:01:30,400
purchased a new product item, which is item

34
00:01:30,401 --> 00:01:32,400
5 in this case, so we will delete the

35
00:01:32,401 --> 00:01:34,900
first item from the list, which is the least

36
00:01:34,933 --> 00:01:37,466
recently purchased, this will create an empty

37
00:01:37,467 --> 00:01:40,000
space in the list. Next, we will push all the

38
00:01:40,001 --> 00:01:42,600
elements to the left by one place, and we'll

39
00:01:42,601 --> 00:01:45,200
insert the new item at the end. Again, you

40
00:01:45,201 --> 00:01:47,133
may note that the most recently purchased

41
00:01:47,134 --> 00:01:48,766
item is at the beginning, while the least

42
00:01:48,767 --> 00:01:51,033
recently purchased item is at the end of the

43
00:01:51,034 --> 00:01:54,100
list. This way when the product four is

44
00:01:54,101 --> 00:01:57,000
purchased next, so we will move it to the end

45
00:01:57,001 --> 00:01:59,500
of the list. This means that when an existing

46
00:01:59,501 --> 00:02:02,466
item is purchased again, so we will just move

47
00:02:02,467 --> 00:02:04,633
it to the end, and the deletion will not

48
00:02:04,634 --> 00:02:08,532
occur. Similarly when item 6 is purchased,

49
00:02:08,533 --> 00:02:10,966
so the first element will be deleted, and the

50
00:02:10,967 --> 00:02:13,833
item 6 will be inserted at the end. In the

51
00:02:13,834 --> 00:02:15,800
same way, the value of 8 and 9 will be

52
00:02:15,833 --> 00:02:18,966
processed accordingly. The important

53
00:02:18,967 --> 00:02:21,700
observation again is that, the least recently

54
00:02:21,701 --> 00:02:23,966
purchased item is always at the beginning, and

55
00:02:23,967 --> 00:02:26,733
the most recently purchased item is at the end.

56
00:02:27,666 --> 00:02:29,900
Once we understood the problem, so now let's

57
00:02:29,901 --> 00:02:32,600
move to the solution. The business requires

58
00:02:32,601 --> 00:02:34,400
that the solution data structure should be

59
00:02:34,401 --> 00:02:36,900
designed, keeping in view the speed aspect.

60
00:02:37,066 --> 00:02:40,066
Moreover, we will also like to keep track of

61
00:02:40,067 --> 00:02:42,966
the first and last element of the list of

62
00:02:42,967 --> 00:02:45,700
values. For speed, we will use the HashMaps,

63
00:02:45,701 --> 00:02:47,866
and keeping track of the first and last

64
00:02:47,867 --> 00:02:50,100
element, we will be using the doubly Linked list,

65
00:02:50,400 --> 00:02:52,900
where we have explicit information about

66
00:02:52,901 --> 00:02:54,933
the first and last element of the list called

67
00:02:54,934 --> 00:02:57,566
the head and the tail respectively. Let us

68
00:02:57,567 --> 00:02:59,666
look at the solution visually, which will

69
00:02:59,667 --> 00:03:01,800
make the implementation quite easy.

70
00:03:03,400 --> 00:03:06,400
Assume the same list of products that we have just

71
00:03:06,401 --> 00:03:09,200
seen. So when the first product is being

72
00:03:09,201 --> 00:03:12,500
purchased, we will make a note of the doubly

73
00:03:12,501 --> 00:03:15,966
Linked list and we'll store it as a node. Since

74
00:03:15,967 --> 00:03:18,266
there will be a single node, so the head and

75
00:03:18,267 --> 00:03:21,033
tail will be pointing to it. Moreover, we

76
00:03:21,034 --> 00:03:24,200
will also make an entry into the HashMap,

77
00:03:24,201 --> 00:03:26,300
where the key will be the value of the node,

78
00:03:26,366 --> 00:03:28,766
and the value will be basically a pointer to

79
00:03:28,767 --> 00:03:31,800
the node. When the next product is being

80
00:03:31,801 --> 00:03:34,300
purchased, we will make an entry at the tail

81
00:03:34,301 --> 00:03:36,500
of the list and we will also add an entry

82
00:03:36,501 --> 00:03:39,100
into the HashMap for that. Again, the key

83
00:03:39,101 --> 00:03:41,766
part will be the value of the node, and the

84
00:03:41,767 --> 00:03:43,900
value part will be the pointer to the node.

85
00:03:43,901 --> 00:03:46,433
In the same way the next two items will also be

86
00:03:46,434 --> 00:03:50,100
inserted. Next, when the item five is being

87
00:03:50,101 --> 00:03:52,666
purchased, so first we will delete the head

88
00:03:52,900 --> 00:03:54,966
and then we will insert the new item at the

89
00:03:54,967 --> 00:03:58,033
tail. Next one item four is being purchased

90
00:03:58,034 --> 00:04:00,266
again, so the node with the value four will

91
00:04:00,267 --> 00:04:02,433
be moved to the tail, and the node with a

92
00:04:02,434 --> 00:04:04,500
value five will be replacing the node with

93
00:04:04,501 --> 00:04:07,700
the value 4. In this case, the map will not

94
00:04:07,701 --> 00:04:10,000
change and only the list will change.

95
00:04:10,001 --> 00:04:11,700
[No Audio]

96
00:04:11,701 --> 00:04:13,966
Please note that, we do not need to replace the

97
00:04:13,967 --> 00:04:16,500
values in the map, because the order inside

98
00:04:16,501 --> 00:04:18,933
the map does not matter. In fact, the map

99
00:04:18,934 --> 00:04:21,132
will help us to determine if a certain value

100
00:04:21,133 --> 00:04:23,900
exists in the map or not. So this will make

101
00:04:23,901 --> 00:04:26,633
the lookup of values in the list quite

102
00:04:26,634 --> 00:04:29,466
faster. This is because the lookup of keys in

103
00:04:29,467 --> 00:04:32,033
the map is very first and almost takes no

104
00:04:32,034 --> 00:04:34,166
time. Next when the item 6 has been

105
00:04:34,167 --> 00:04:36,533
purchased, so since the item does not exist

106
00:04:36,534 --> 00:04:38,900
in the list, therefore, we will remove one

107
00:04:38,933 --> 00:04:41,200
element from the list, which will be the least

108
00:04:41,201 --> 00:04:43,466
recently purchased, and then the new item will

109
00:04:43,467 --> 00:04:46,400
be inserted at the tail. In this way the

110
00:04:46,401 --> 00:04:48,533
whole process will continue. The important

111
00:04:48,534 --> 00:04:50,866
points to note are, number one, the order of

112
00:04:50,867 --> 00:04:53,966
the map entries does not matter. Number two,

113
00:04:54,133 --> 00:04:56,766
the map is just used to quickly look if some

114
00:04:56,767 --> 00:04:59,400
value exist or not. Number three, the head

115
00:04:59,401 --> 00:05:01,866
and tail gives explicit information regarding

116
00:05:01,867 --> 00:05:03,933
the least recently used and most recently

117
00:05:03,934 --> 00:05:07,266
purchased items. Number four, when a new item

118
00:05:07,267 --> 00:05:09,166
has been purchased, which is not already in

119
00:05:09,167 --> 00:05:11,366
the list. So we will delete one of one of the

120
00:05:11,367 --> 00:05:13,600
nodes, and we'll insert a new note at the

121
00:05:13,601 --> 00:05:16,666
tail. And finally, number five, if the item

122
00:05:16,667 --> 00:05:18,300
that is being purchased is already in the

123
00:05:18,301 --> 00:05:20,733
list, then we will just move it to the end

124
00:05:20,766 --> 00:05:23,100
without making any updation in the map.

125
00:05:24,400 --> 00:05:26,433
This is enough explanation, and the rest of the

126
00:05:26,434 --> 00:05:28,300
details will become clear to us during the

127
00:05:28,301 --> 00:05:30,133
implementation. So let's start with the

128
00:05:30,134 --> 00:05:32,833
implementation. I am starting with the code

129
00:05:32,834 --> 00:05:35,333
of doubly Linked list that we have seen in one of

130
00:05:35,334 --> 00:05:38,100
the previous sections in detail. There are

131
00:05:38,101 --> 00:05:40,733
very minor changes in this code. The first

132
00:05:40,734 --> 00:05:42,700
change is that, I'm only considering the

133
00:05:42,701 --> 00:05:46,500
functions of push_back and remove_front,

134
00:05:46,900 --> 00:05:48,533
because I only need these

135
00:05:48,534 --> 00:05:51,633
two functions in this particular problem. So

136
00:05:51,634 --> 00:05:54,066
the extra functions of push_front and remove_back

137
00:05:54,067 --> 00:05:56,566
are not part of this code. Moreover, I

138
00:05:56,567 --> 00:05:58,900
am also not considering the print function in this code.

139
00:05:58,901 --> 00:06:00,733
[No Audio]

140
00:06:00,734 --> 00:06:02,166
The second minor change is that,

141
00:06:02,167 --> 00:06:04,333
the two functions are returning a link to the

142
00:06:04,334 --> 00:06:07,033
node, and an optional link to node in case of

143
00:06:07,066 --> 00:06:09,766
the remove functions, the rest of the details

144
00:06:09,767 --> 00:06:12,266
are exactly the same, and now we will use

145
00:06:12,300 --> 00:06:14,833
this implementation in our code. I will start

146
00:06:14,834 --> 00:06:17,733
by declaring a struct which will derive the Debug.

147
00:06:17,734 --> 00:06:25,366
[No Audio]

148
00:06:25,367 --> 00:06:27,466
This struct will contain the HashMap and the

149
00:06:27,467 --> 00:06:30,700
list, and I will call it our most recently

150
00:06:30,733 --> 00:06:33,733
purchased items or MRP_Item for short.

151
00:06:33,734 --> 00:06:40,300
[No Audio]

152
00:06:40,301 --> 00:06:42,366
This struct will contains all the necessary

153
00:06:42,367 --> 00:06:45,000
stuff, that is the HashMap and the doubly Linked list.

154
00:06:45,001 --> 00:06:46,800
So let me declare the fields.

155
00:06:46,801 --> 00:06:55,300
[No Audio]

156
00:06:55,301 --> 00:06:57,266
It will also have information about the

157
00:06:57,267 --> 00:06:59,100
current size of the list and the maximum

158
00:06:59,101 --> 00:07:00,400
capacity of the list.

159
00:07:00,401 --> 00:07:06,866
[No Audio]

160
00:07:06,867 --> 00:07:09,066
Let us now define the implementation block of

161
00:07:09,067 --> 00:07:10,600
the MRP_item.

162
00:07:10,601 --> 00:07:16,433
[No Audio]

163
00:07:16,434 --> 00:07:18,766
First we will define a new function, the input

164
00:07:18,767 --> 00:07:20,966
will be the capacity that we want to have for

165
00:07:20,967 --> 00:07:23,100
the list, and the output will be the type itself.

166
00:07:23,101 --> 00:07:30,400
[No Audio]

167
00:07:30,401 --> 00:07:32,666
Inside the function, we will return Self with

168
00:07:32,667 --> 00:07:33,966
some default values.

169
00:07:33,967 --> 00:07:40,400
[No Audio]

170
00:07:40,401 --> 00:07:42,900
The map will be a new empty map and the list

171
00:07:42,901 --> 00:07:46,200
will be a new empty list, the size will be 0

172
00:07:46,201 --> 00:07:48,800
and the capacity will be set to that of capacity.

173
00:07:48,801 --> 00:07:55,266
[No Audio]

174
00:07:55,267 --> 00:07:57,666
Next, we will define a purchased function.

175
00:07:57,667 --> 00:07:59,700
This is going to be the main function that we

176
00:07:59,701 --> 00:08:02,266
will be using, this function will update the

177
00:08:02,267 --> 00:08:05,833
list and the map based on a new item that is

178
00:08:05,834 --> 00:08:07,933
being purchased. The input to the function

179
00:08:07,934 --> 00:08:09,933
will be a mutable reference to Self, and the

180
00:08:09,934 --> 00:08:12,000
product or item that has been purchased.

181
00:08:12,001 --> 00:08:20,933
[No Audio]

182
00:08:20,934 --> 00:08:23,133
Inside the function, we will first check if

183
00:08:23,134 --> 00:08:25,666
our list already contains the product or not.

184
00:08:26,000 --> 00:08:28,266
For this, we will check if there is an entry

185
00:08:28,267 --> 00:08:30,966
in the HashMap for the product. This can be

186
00:08:30,967 --> 00:08:33,000
done using the get function with an input

187
00:08:33,001 --> 00:08:35,299
being the reference to the product_id,

188
00:08:35,332 --> 00:08:37,366
this returns an Option.

189
00:08:37,367 --> 00:08:46,800
[No Audio]

190
00:08:46,801 --> 00:08:49,100
Please note again, that the HashMap makes the

191
00:08:49,101 --> 00:08:51,200
operation of looking into the values of the

192
00:08:51,201 --> 00:08:54,600
list super fast. If we do not use the

193
00:08:54,601 --> 00:08:56,966
HashMaps, then we will traverse the whole list

194
00:08:56,967 --> 00:08:59,133
from head to tail in order to determine if a

195
00:08:59,134 --> 00:09:01,800
value exists or not, which will be a costly

196
00:09:01,801 --> 00:09:05,766
operation if the list is long. If the value

197
00:09:05,767 --> 00:09:08,066
already exists, then we will move it to the

198
00:09:08,067 --> 00:09:11,233
tail of the list. We currently do not have a

199
00:09:11,234 --> 00:09:13,666
function, which given a node, moves it to the

200
00:09:13,667 --> 00:09:15,900
tail of the list. So this means that, we need

201
00:09:15,901 --> 00:09:18,166
to implement this function which given a node

202
00:09:18,167 --> 00:09:20,566
will move it to the end or to the tail of the

203
00:09:20,567 --> 00:09:23,100
list. We will look into the implementation of

204
00:09:23,101 --> 00:09:25,033
this function in the next tutorial, because

205
00:09:25,034 --> 00:09:26,966
there are quite a few details, and coding left

206
00:09:26,967 --> 00:09:28,966
and covering all of them in a single tutorial,

207
00:09:28,967 --> 00:09:31,500
may be a bit hard to digest and comprehend.

208
00:09:31,800 --> 00:09:33,900
So do come back again fresh and until then

209
00:09:33,901 --> 00:09:35,666
enjoy Rust programming.

210
00:09:35,667 --> 00:09:40,700
[No Audio]