Smart as a bag of rocks

For my second project in CS2, I was given the following assignment:


Implement a new ADT called a bag with receipts.


The specification for the class of bag with receipts differs from a
typical bag in the text in the following ways:

• The add() operation will return a unique integer receipt for each object inserted into the container. Note that when an object associated with a given receipt is removed from the container, then that receipt value can (and should) be reused for a subsequently added object.

• The remove() operation takes an integer argument—the receipt associated with the object to remove from the container. In addition, the remove() operation will return a copy of the object that has been removed.

The design for the class of bag with receipts will require keeping
track of the objects and their associated receipts. One approach is to
use parallel arrays. Parallel arrays involve keeping two or more
arrays that are the same size and using the same index to access parts
of the same "object" in that data store.


The data storage that you use for your bag with receipts class must be
array-based and have dynamic size.


You are required to design and implement a complete testing suite. The
tests you design must test all aspects of the code in your bag with
receipts class.

I kinda thought that my implementation of the data type might be a bit dumb, hence the title. Feel free to rip the code apart!

ReceiptBagInterface.h:

```
/**
* @file ReceiptBagInterface.cpp
*/

#ifndef RECEIPT_BAG_INTERFACE
#define RECEIPT_BAG_INTERFACE

#include
#include

/** @class ReceiptBagInterface ReceiptBagInterface.h "ReceiptBagInterface.h"
*
Definition of ReceiptBagInterface class template. /
template
class ReceiptBagInterface {
public:

/** Virtual destructor. */
virtual ~ReceiptBagInterface() {}

/** Gets the current number of entries in this bag.
*
* @return The integer

Single responsibility principle

The add method violates SRP by doing two things:
ensure capacity, add item.
It would be better to move the logic of ensuring capacity to a dedicated ensureCapacity method, taking an integer as the desired target size.

Memory management

The remove method doesn't reduce capacity when it becomes underused.
For example if 1000 items are added,
and subsequently the last 900 items are removed,
then you'll end up with a mostly unused capacity, still taking up memory.
Of course, shrinking the storage can be expensive too,
as you'd have to allocate the new storage, and then copy the elements.
An alternative approach might be to store pointers instead,
the storage of which should be small,
and when removing an element, just delete its pointer.
Unfortunately, either of these approaches would significantly complicate your task.
(I'm not sure whether shrinking the capacity as needed is part of your assignment.)

Validating post-conditions

The add method loops over elements to find a suitable spot and return the index of that spot.
The method expects to always find a spot, and so you have this at the very end:

// should theoretically never get here
return -1;

The assumption that execution is not supposed to reach this part is a kind of post-condition.
Assertions are a good approach for validating post-conditions.
So I recommend to insert something like this before the return statement:

assert(0);  // presumed unreachable

Missing the specs


The remove() operation takes an integer argument—the receipt associated with the object to remove from the container. In addition, the remove() operation will return a copy of the object that has been removed.

The implementation returns a boolean instead of a copy of the removed item.

Overshooting the specs

You implemented a lot more methods than mentioned in the specs.
That's ok, if it helps your testing.
But the extra methods should not be part of the public API.
(Unless, of course, the extra methods are already part of the "typical bag" in this course.)

Naming

Many of the methods and variables have more commonly used names,
that I would recommend to adopt:

• getCurrentSize() -> size()

• getFrequencyOf() -> count()

• maxItems -> capacity

I would also rename the ItemType template parameter to simply Item.

Testing


You are required to design and implement a complete testing suite. The tests you design must test all aspects of the code in your bag with receipts class.

I see at least one important test case missing:
reusing of receipt ids.

In general, the way you tested doesn't strike me as a "complete testing suite".
Your prof might be looking for something more to be impressed.

Simplify unused else

In the remove method you have this:

if(inUse[receipt])
{         
    // ...
    return true;
}
else return false;

You can drop the else and write just return false there.

StackExchange Code Review Q#80648, answer score: 8