(E) Moving cards¶

Goal: I will learn more about dynamic memory management and the use of pointers.

Instructions: Retrieve the code template: templates/08/cards/ -> student/08/cards/.

Note

You can submit the assignment even if you are not able to implement all of the methods. You will get part of the points if you have implemented at least the methods get_topmost, add, and remove.

However, in order to pass the automated tests, you have to create empty dummy-implementations of all the methods. You can easily do this in Qt Creator by right-clicking the name of the method in the .hh file of the class, and taking a look at the contents of the ”Refactor” menu.

There is a card game in which you move cards into the deck and out of it according to certain rules. Let us implement a class that allows us to move cards in the deck only according to the rules of the game and to print the contents of the deck. We will simplify the assignment by numbering the cards and by referring to each card by its number, so that we can concentrate on the data structure itself without paying attention to the details of input handling.

We will create a data structure where you can store integers. The file cards.hh defines the interface for the class we are going to implement, and you must not edit it. This means that you must not edit the public part of the class, but if you wish, you can edit the private methods and member variables of the class. Since we are practicing dynamic memory management, your task is to implement the class without using the STL containers, string, or the C++ array.

Rules¶

At first, the card deck is empty. You can move cards in four different ways:

You can add a new card on the top of the deck. The number of that card is passed a parameter for the adding operation.
You can remove the topmost card of the deck. The number of the topmost card is passed from the method to its caller (in the reference parameter id).
You can move the bottom card of the deck to the top.
You can move the topmost card of the deck to the bottom.

For each action mentioned above, you will implement a method, the definition of which is given in the class interface file.

Also, to simplify the testing, there is a method for printing the card deck (print_from_top_to_bottom). The most eager students also have a chance to either practice pointer handling or revise recursion by implementing a second, slightly more challenging printing method (print_from_bottom_to_top).

Testing a class¶

There is a simple test for the class in the file main.cpp. Here is an example of how the class should work with the test main program we gave you:

constructor
Enter amount of test cards: 5

print_from_top_to_bottom (deck is empty)

add * n

print_from_top_to_bottom
1: 4
2: 3
3: 2
4: 1
5: 0

bottom_to_top * 2

print_from_top_to_bottom
1: 1
2: 0
3: 4
4: 3
5: 2

top_to_bottom * 1

print_from_top_to_bottom
1: 0
2: 4
3: 3
4: 2
5: 1

print_from_bottom_to_top
1: 1
2: 2
3: 3
4: 4
5: 0

remove 0
remove 4
remove 3
remove 2
remove 1

destructor

The ready-made testing is not complete, but you can start with it. You are free to edit the testing main program, and a more exhaustive testing will help you in writing your program. The automated test system tests the class without the main program. This means that the system does not care what you are doing in your own testing main program. It might be a good idea to save some of the original tests so that you can compare their prints with the model print above.

Tips for completing the assignment:

First, have a look at the main program you were given.
To begin, just implement two most necessary methods (one will edit the card deck, and the other will test the result). Use comments to take all the calls to other methods off the main program. For this purpose, it is handy to use the multi-line comment /* this part is taken off with comments */.
When implementing each operation, please remember what the situations are that you need to consider when handling a linked data structure (see the summary of the previous material section).
To pass automated tests, use the parameter stream s for printing, not cout.
Automated tests require proper use of dynamic memory management, e.g. all allocated memory must be deallocated. These tests use valgrind tool that will be introduced on the next round.
If you want to practice more and decide to implement the method print_from_bottom_to_top, you can choose from several implementation solutions:
1. Recursion: This is easy to implement, and revising recursion is useful, but you will not learn anything new about pointers. Start by thinking of the list as a recursive data structure, or by finding a way to split it into several smaller sub-problems that are similar to the original one. Please note that in your private class interface, you have a pre-made function (recursive_print) that is meant to call itself recursively.
2. Doubly-linked list: You will get more practice on handling pointers, but it will take more effort than the recursive solution. The idea is for you to insert an additional pointer field into the struct Card_data that links the cards to each other also in the opposite (backward) direction. These pointers must naturally be updated in all the methods that modify the data structure.
3. Of course, it is also possible to print iteratively without implementing a doubly-linked list. It will just take a lot more going through the list backwards and then forwards, which is quite inefficient.

A+ presents the exercise submission form here.