HW 3.

Storage implementation (no additional tests)

/*
  Author:
  Description: HW3. Storage bookkeeping
*/ 

#include <iostream>
#include <cassert>
#include <cstdlib>
using namespace std;

struct Entry {
  int id;
  int count;
};

class Storage {
  static const int N = 1024;
  Entry buf[N];
  int card;

public:
  void empty();
  int number_of_distinct_items();
  
  int count(int id);
  void add(int id);
  void remove(int id);

  bool pick_an_item(int &id); 
};

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(); 

}

void Storage::empty() {
  card = 0;
}

int Storage::number_of_distinct_items() {
  return card;
}

int Storage::count(int id) {
  for (int i = 0; i < card; i++) {
    if (buf[i].id == id) return buf[i].count;
  }
  return 0;
}

void Storage::add(int id) {
  for (int i = 0; i < card; i++) {
    if (buf[i].id == id) {
      buf[i].count ++;
      return;
    }
  }
  // if id is not found, then if there is a room in the buffer,
  // add a new entry at the end:
  if (card < N) {
    buf[card].id = id;
    buf[card].count = 1;
    card ++;
  }
}

void Storage::remove(int id) {
  for (int i = 0; i < card; i++) {
    if (buf[i].id == id) {
      // count must be positive
      assert(buf[i].count > 0);
      // remove ine item of thie type
      buf[i].count --;
   
      if (buf[i].count <= 0) {
        // if the last item if this type has been removed, compact the array
        for (int j = i; j < card-1; j++) {
          buf[j].id = buf[j+1].id;
          buf[j].count = buf[j+1].count;
        }
        // decrement the cardinality
        card --;
      }

      return;
    }
  }
}

bool Storage::pick_an_item(int &id) {
  if (card > 0) {
    id = buf[rand() % card].id;
    return true;
  }
  return false;
}

Test 1
======

Adding 20 items: 33 13 35 19 12 12 26 27 18 28 28 26 38 21 22 37 26 33 33 27 

They are:

27 : 2
12 : 2
37 : 1
28 : 2
35 : 1
38 : 1
21 : 1
22 : 1
26 : 3
13 : 1
18 : 1
19 : 1
33 : 3

Total of 20 items