[No Audio]
In the last tutorial, we started with the
implementation of the solution, and this is
where we left the code. We were looking at
the implementation of the move_to_tail function.
So let's start coding it.
We will start by declaring the move_to_tail function.
[No Audio]
The input will be a mutable reference to the
list itself, and a reference to the Node that
we want to move to the tail. Next, we will
grab the information of the Next and Previous
Nodes of the given Node. We would also want
to own these Nodes. To grab the previous Node
information, we will call the borrow function
on Node to borrow it, and we'll access its
previous field which contains the previous
Node information. Next, we will use the
as_ref function for grabbing the
contents of the Node, that is being the
option. This will give us the previous Node
which will not map to the clone copy of the cell.
[No Audio]
This means now that, we now own the previous
Node, and therefore, we can change its
contents. In the same way, we will also grab
the next Node information.
[No Audio]
The previous now contains the previous of the
Node, which corresponds to the item purchased,
and the next contains the next Node. There
can be now four possibilities for the
previous and next. To check for these
possibilities we will use a match on the
previous and next. The first possibility will
be that the previous and next are both None.
[No Audio]
This can only happen if the Node under
investigation is the only Node in the list.
In this case, we do not need to do anything, so
we will keep right side body of the arm empty.
[No Audio]
The second case is that, there is some
previous, but there is nothing in the next.
This will happen when the Node is already at
the tail, because the next of the tail
is always empty. This again means that we do
not need to do anything, because the Node is
already at the tail. So we will keep the
right side of the of the arm empty.
[No Audio]
The next case will be when there is nothing in
the previous, but there is some Node in the next.
This means that the Node we
want to move is at the head of the list, since
the head has None in the previous pointer,
and the next is Some Node.
Let us visually see how
we will move the head to the tail. Consider
this list, where the Node with a value of
3 is at the head of the list,
which we intend to move to the end of the list.
So first we will determine the next and the
previous nodes with respect, with respect to
the Node, which is the Head node in this case.
Next we will update the head information for
the whole list. So we will take out the
previous head from the list, we will update
its next pointer to that of None.
[No Audio]
We will also update the previous
of the next Node as None,
because it is going to be the new head of the
list, and the previous of head is always None.
Finally, we will update the head to that of
the next Node. The red colors in the slide
shows the necessary updates that we need to make.
[No Audio]
Next, we will move the Node that we
have just taken out to the end of the list.
So, let us now see what updations we will
need to make in this regards. We will first
update the next of the prev_tail to that
of the Node shown in the red color. Following
this, we will set the previous pointer of the
Node to that of the prev_tail, and finally
we will update the Tail of the list to that
of the Node, let us now see the implementation.
We will first update the next
of the Nodes. So for that we will borrow it
mutably by calling the borrow_mut
function on the Node, and will update
it's next to that of None.
[No Audio]
Following this, we will update the previous
smart pointer of the next Node to that of None also.
[No Audio]
Finally, we will update the head, so that it
points to the next by using the clone.
Please note that the scope of the next variable is
limited to the scope of this match, and it
will not exist when the function ends. This
does not mean that the head will be a
dangling pointer when the function ends,
because using the clone makes sure that it
owns the data, because it creates a shared ownership.
If you still feel uncomfortable,
then I would suggest you again look at the
details in the section of smart pointers.
Next, we will make the necessary updates to the
tail of the list. First, we will create a
pointer to the tail. We want to have a
reference to the tail Node, therefore we will
use the as_ref function on the self.tail,
and then we'll unwrap it.
[No Audio]
Next, we will update the next pointer of the previous
tail to that of Node.
[No Audio]
We will next, set the previous of the Node to
that of the prev_tail.
[No Audio]
Finally, we will update the tail to that of
the Node itself.
[No Audio]
The last case will be when there is some
previous and some next Node. This means that
the Node we want to move to the end is in the
middle of the list. Let us visually see what
updation will be required in this case.
First, we will determine the Next and
Previous Nodes with respect to the Node that
we wish to move to the end. Next, we will
take it out from the middle, and we'll set the
pointers of the previous and next, so that the
list becomes connected again. To make the
connections, we will first set the next of
the previous Node to that of the next Node.
Then we will set the previous of the next
Node to that of the previous Node. Moreover,
we will also set the next of the Node to None,
since it is going to be added at the end, and
we know that the next of the tail is None.
We will next, put the Node at the end and we'll set
the pointers accordingly. The next of the
prev_tail will become the Node itself, the
Node previous, the Node's previous will be the
prev_tail, and finally the new
tail will be the Node itself. Let us look at
the implementation of the same in code.
[No Audio]
We will first set the next of the Node to that
of None. Following this, we will set the next
of the previous Node to that of the next Node.
[No Audio]
The previous of the next Node will
become the previous Node.
[No Audio]
Next, we will have a reference to the prev_tail.
[No Audio]
The prev_tail next will become the Node.
[No Audio]
The previous of the Node will be the prev_tail.
[No Audio]
And finally, we will update the tail to that of the Node.
[No Audio]
Okay done.
Now, let us call it from the purchased
function. We were here in the purchase
function, where we looked for a prod_id
in the HashMap, and if there is
some already existing entry, then we will
obtain the corresponding Node from the list,
and then we will move it to the end.
To move the Node to the end, we will simply call the
move_to_tail function,
that we just wrote with the Node as an input.
If the Node is not already in the HashMap,
then we will check first, if the list has some
space for adding the new product or not.
If the list has no space, then we will remove the
head from the list, and will then proceed with
inserting the new element at the tail.
[No Audio]
So let us add a condition to check if the list has
some space or not. Please note that I am
intentionally writing the code as greater
than or equal to and not equal to, and the
reason will become clear to us in a moment.
I would like to remove the head, and we'll store
it in a variable.
[No Audio]
Next, I will remove the prod_id
that is associated with the Node from the
HashMap by calling the remove
function on the HashMap.
[No Audio]
The remove function expects a reference, so
therefore we provided a reference. Next,
if the list is not at the full capacity, then
we will simply add the prod_id at the end
of the list using the push_back
function of the list, and we will store the
newly created Node in the variable of Node.
[No Audio]
Next, we will update update the map also, so
that it contains an entry for the prod_id,
and the Node is the value part.
[No Audio]
Finally, we will update the size.
[No Audio]
Since we are updating the size at the end of
the function, therefore we use the condition
of greater than or equal to at the start of
the code to check if the list is at capacity or not.
If we were updating the size at the
start before inserting the Node, then we would
be using the condition of equality.
Finally, I will I will add and declare a print
function for printing the list of items.
[No Audio]
The input to the function will be a reference to self.
[No Audio]
We will first define a variable called
traversal which will be pointing towards the
head of the list.
[No Audio]
Next, we will iterate until the traversal
becomes empty, and during each iteration we
will update the traversal to that of the next,
of the next Node.
I will create a while loop for iterating.
Inside the loop, I will create
a variable called temp which will contain a
clone of the traversal.
[No Audio]
Then I will print the prod_id
associated with the temp, which is the current
Node in our traversal of the list.
[No Audio]
Finally, I will update the traversal to that
of the next Node in the list.
[No Audio]
Outside the while, I will add an extra
println statement, so that each time the
list is being displayed on a separate line.
[No Audio]
Now let us test the code in the main, I will
first create a new MRP_item
instance, and it will have a capacity of size 3.
Let us add an item to the list by
calling the purchase function and display the
list in cargo run.
[No Audio]
Let us add a couple of more items to the list
and cargo run again.
[No Audio]
You may note that, the newly purchased items
are being added at the end of the list. Let
us now purchase one more item, and print and
cargo run again.
[No Audio]
The newly purchased item has been added at
the end of the list, and the least recently
purchased item which was at the beginning has
been removed, because the list reached to its
capacity. You can test with different inputs
and see the results for yourselves. That
brings us to the end of this tutorial. I hope
you would have enjoyed coding with me this
problem. The takeaways is that the HashMaps
are quite handy for quick searching through
items in the list. Do can make again for more
and until then happy Rust programming
[No Audio]