HW 3. Storage bookkeeping

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.

The task.

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:

• empty the storage
• ask how many different types of items are in the storage (that is, how many distinct IDs are there?)
• ask how many items of the kind id are in the storage
• add an item of the kind id
• remove an item of the kind id
• pick one item at random from the storage (if there is any)

Consider an example

After adding items with the IDs: 51, 1005, 51, 51, 267,
the storage should contain:

• three copies of 51,
• one copy of 1005,
• and one copy of 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.

Testing your 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:

• Adding an element of the type id, always increases their count by one.
• After adding N items of the type id, the storage contains exactly N of them.
• Trying to remove an item that is not in the storage, does not remove some other item instead (by mistake).
• Trying to remove from an empty storage does not cause an error.
• Picking an arbitrary item from the storage really gives you an item that is present in the storage.
• Trying to add too many items (beyond the capacity of the Storage does not cause an error).

Test 1

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