HW 3. Storage bookkeeping

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.

Storage

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:

Consider an example

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

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:

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:

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