[No Audio]
Welcome back again. In this tutorial, we will
be looking at an interesting problem, which
we will be solving using doubly Linked lists
and HashMaps, the scenario goes like this.
A business is interesting in knowing the
products that has been purchased most
recently by a customer, they will use this
information in their promotional and
marketing campaigns. They would like to store
this information in a suitable data structure,
where they can easily determine a list of
some predetermined number of most recently
purchase products. The business is also very
critical about the speed of the retrieved
information from the data structure. Let us
look at the problem in a bit more detail
using slides. Consider this to be the list of
products that are being purchased in the
order given in the list. We would like to
store information about four most recently
purchased items or products. When the item
1 is being purchased, we will store it in
the list. Next item 2 is being purchased,
so we will store 2. In the same way, we have
the information about the next two items
which are being purchased. At this stage, the
list is at full capacity, and most recently
item that is being purchased is at the end of
the list. While the least recently purchased
or the oldest purchased item is at the
beginning of the list. Now when the customer
purchased a new product item, which is item
5 in this case, so we will delete the
first item from the list, which is the least
recently purchased, this will create an empty
space in the list. Next, we will push all the
elements to the left by one place, and we'll
insert the new item at the end. Again, you
may note that the most recently purchased
item is at the beginning, while the least
recently purchased item is at the end of the
list. This way when the product four is
purchased next, so we will move it to the end
of the list. This means that when an existing
item is purchased again, so we will just move
it to the end, and the deletion will not
occur. Similarly when item 6 is purchased,
so the first element will be deleted, and the
item 6 will be inserted at the end. In the
same way, the value of 8 and 9 will be
processed accordingly. The important
observation again is that, the least recently
purchased item is always at the beginning, and
the most recently purchased item is at the end.
Once we understood the problem, so now let's
move to the solution. The business requires
that the solution data structure should be
designed, keeping in view the speed aspect.
Moreover, we will also like to keep track of
the first and last element of the list of
values. For speed, we will use the HashMaps,
and keeping track of the first and last
element, we will be using the doubly Linked list,
where we have explicit information about
the first and last element of the list called
the head and the tail respectively. Let us
look at the solution visually, which will
make the implementation quite easy.
Assume the same list of products that we have just
seen. So when the first product is being
purchased, we will make a note of the doubly
Linked list and we'll store it as a node. Since
there will be a single node, so the head and
tail will be pointing to it. Moreover, we
will also make an entry into the HashMap,
where the key will be the value of the node,
and the value will be basically a pointer to
the node. When the next product is being
purchased, we will make an entry at the tail
of the list and we will also add an entry
into the HashMap for that. Again, the key
part will be the value of the node, and the
value part will be the pointer to the node.
In the same way the next two items will also be
inserted. Next, when the item five is being
purchased, so first we will delete the head
and then we will insert the new item at the
tail. Next one item four is being purchased
again, so the node with the value four will
be moved to the tail, and the node with a
value five will be replacing the node with
the value 4. In this case, the map will not
change and only the list will change.
[No Audio]
Please note that, we do not need to replace the
values in the map, because the order inside
the map does not matter. In fact, the map
will help us to determine if a certain value
exists in the map or not. So this will make
the lookup of values in the list quite
faster. This is because the lookup of keys in
the map is very first and almost takes no
time. Next when the item 6 has been
purchased, so since the item does not exist
in the list, therefore, we will remove one
element from the list, which will be the least
recently purchased, and then the new item will
be inserted at the tail. In this way the
whole process will continue. The important
points to note are, number one, the order of
the map entries does not matter. Number two,
the map is just used to quickly look if some
value exist or not. Number three, the head
and tail gives explicit information regarding
the least recently used and most recently
purchased items. Number four, when a new item
has been purchased, which is not already in
the list. So we will delete one of one of the
nodes, and we'll insert a new note at the
tail. And finally, number five, if the item
that is being purchased is already in the
list, then we will just move it to the end
without making any updation in the map.
This is enough explanation, and the rest of the
details will become clear to us during the
implementation. So let's start with the
implementation. I am starting with the code
of doubly Linked list that we have seen in one of
the previous sections in detail. There are
very minor changes in this code. The first
change is that, I'm only considering the
functions of push_back and remove_front,
because I only need these
two functions in this particular problem. So
the extra functions of push_front and remove_back
are not part of this code. Moreover, I
am also not considering the print function in this code.
[No Audio]
The second minor change is that,
the two functions are returning a link to the
node, and an optional link to node in case of
the remove functions, the rest of the details
are exactly the same, and now we will use
this implementation in our code. I will start
by declaring a struct which will derive the Debug.
[No Audio]
This struct will contain the HashMap and the
list, and I will call it our most recently
purchased items or MRP_Item for short.
[No Audio]
This struct will contains all the necessary
stuff, that is the HashMap and the doubly Linked list.
So let me declare the fields.
[No Audio]
It will also have information about the
current size of the list and the maximum
capacity of the list.
[No Audio]
Let us now define the implementation block of
the MRP_item.
[No Audio]
First we will define a new function, the input
will be the capacity that we want to have for
the list, and the output will be the type itself.
[No Audio]
Inside the function, we will return Self with
some default values.
[No Audio]
The map will be a new empty map and the list
will be a new empty list, the size will be 0
and the capacity will be set to that of capacity.
[No Audio]
Next, we will define a purchased function.
This is going to be the main function that we
will be using, this function will update the
list and the map based on a new item that is
being purchased. The input to the function
will be a mutable reference to Self, and the
product or item that has been purchased.
[No Audio]
Inside the function, we will first check if
our list already contains the product or not.
For this, we will check if there is an entry
in the HashMap for the product. This can be
done using the get function with an input
being the reference to the product_id,
this returns an Option.
[No Audio]
Please note again, that the HashMap makes the
operation of looking into the values of the
list super fast. If we do not use the
HashMaps, then we will traverse the whole list
from head to tail in order to determine if a
value exists or not, which will be a costly
operation if the list is long. If the value
already exists, then we will move it to the
tail of the list. We currently do not have a
function, which given a node, moves it to the
tail of the list. So this means that, we need
to implement this function which given a node
will move it to the end or to the tail of the
list. We will look into the implementation of
this function in the next tutorial, because
there are quite a few details, and coding left
and covering all of them in a single tutorial,
may be a bit hard to digest and comprehend.
So do come back again fresh and until then
enjoy Rust programming.
[No Audio]