Due Saturday, April 4, by 11:59pm (Midnight).
There is only one task and only one program to be submitted.
The program should start with a comment that contains your name and a short program description, for example:
/*
Author: Your Name
Description: HW 1. Task 1. Printing a rectangle
.. you may add a more detailed description if it's necessary ..
*/
If a program does not do what it’s supposed to do (e.g. there are some bugs, it behaves differently, or maybe even does not compile), then its “incomplete” status must be clearly mentioned in the comment to the program. In this case, please briefly describe what is implemented, and what is not.
We are going to implement an abstract data type Storage
.
It is quite similar to the set of integers IntSet
that we developed in class.
With the only one difference: The set of integers did not care how many times you add the same element to the set,
it was counted only once.
This Storage
data type should be able to store the same element multiple times, and count how many
copies of this element it contains.
Imagine that you have to keep track of the items in a certain storehouse. All items have a barcode, which we will call the item ID number. All identical items have identical ID numbers.
Thus the bookkeeping task reduces to keeping track of how many times the items with the different ID were put in the storage, and removed from it.
We want to be able to:
id
are in the storageid
id
Consider an example
After adding items with the IDs: 51
, 1005
, 51
, 51
, 267
,
the storage should contain:
51
,1005
,267
.Implementation
We may assume that the number if distinct IDs will be not more than 1024.
The IDs themselves can be as large as you want, as long as they are representable
by the type int
.
Also, if you want, you may assume that the total capacity (the total number of items stored)
is also bounded by some integer. If you make this assumption, please mention it in your code.
The abstract data type should be implemented as a class, with all member variables declared private, and providing the following public member functions (methods):
// make the storage empty
void empty();
// return how many items with distinct IDs there are in the storage
int number_of_distinct_items();
// how many copies of the item `id` are stored
int count(int id);
// add an item `id`
void add(int id);
// remove an item `id`
void remove(int id);
// if the storage is empty, return false,
// otherwise return true, and update the variable `id`
// with the ID of some item stored.
bool pick_an_item(int &id);
The last function is important to be able to iterate through the storage, you will see how it is used in the next section, where we test the implementation.
The main
function should test the class Storage
, verifying that the implementation is correct,
that the items are added and removed correctly, and nothing gets lost.
Choose yourself, what properties can be tested, and how to implement such tests.
Some possible properties to test are:
id
, always increases their count by one.id
, the storage contains exactly N of them.Storage
does not cause an error).Here is one, quite complex test you may use, although you don’t have to.
Note that just one single test is not enough, you have to implement some other test yourself
This test:
First, fills the storage with 20 random items. Some of them can be identical.
Then, using the function pick_an_item
, we pick an item and remove all its copies from the storage.
We also print how many copies of that item were there.
We keep removing the items until the storage is empty.
In the end, we assert that the total number of items removed from the storage is exactly equal to the number of items originally added in the storage.
void test1() {
Storage storage;
storage.empty();
// Put m random items in the storage
int m = 20;
cout << "Adding " << m << " items: ";
for(int i = 0; i < m; i++) {
int id = 10 + rand() % 30;
storage.add(id);
cout << id << ' ';
}
cout << endl << endl;
// Now, empty the storage iteratively, printing out
// how many items of each kind was there:
cout << "They are:" << endl << endl;
int total_removed = 0;
while (true) {
int id;
if (storage.pick_an_item(id)) {
int count = storage.count(id);
while(storage.count(id) > 0) {
storage.remove(id);
total_removed ++;
}
cout << id << " : " << count << endl;
}
else
break;
}
cout << endl;
cout << "Total of " << total_removed << " items " << endl;
assert (total_removed == m);
cout << endl;
}
int main() {
srand(time(NULL));
cout << endl;
cout << "Test 1" << endl;
cout << "======" << endl << endl;
test1();
}
Test 1
======
Adding 20 items: 34 13 13 34 35 32 32 37 10 12 24 10 29 13 21 33 31 24 15 22
They are:
35 : 1
29 : 1
34 : 2
15 : 1
12 : 1
32 : 2
31 : 1
10 : 2
37 : 1
33 : 1
24 : 2
21 : 1
22 : 1
13 : 3
Total of 20 items