# 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 <cstdint>
#include <vector>

/** @class ReceiptBagInterface ReceiptBagInterface.h "ReceiptBagInterface.h"
*
*  Definition of ReceiptBagInterface class template. */
template <typename ItemType>
class ReceiptBagInterface {
public:

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

/** Gets the current number of entries in this bag.
*
*  @return The integer number of entries currently in the bag. */
virtual int getCurrentSize() const = 0;

/** Sees whether this bag is empty.
*
*  @return True if the bag is empty, or false if not. */
virtual bool isEmpty() const = 0;

/** Adds a new entry to this bag.
*
*  @post If successful, newEntry is stored in the bag and the
*        count of items in the bag has increased by 1.
*
*  @param newEntry The object to be added as a new entry.
*
*  @return True if addition was successful, or false if not. */
virtual int add(const ItemType& newEntry) = 0;

/** Removes one occurrence of a given entry from this bag, if
*  possible.
*
*  @post If successful, anEntry has been removed from the bag and
*        the count of items in the bag has decreased by 1.
*
*  @param anEntry The value of the entry to be removed.
*
*  @return True if removal was successful, or false if not. */
virtual bool remove(const size_t& receipt) = 0;

/** Removes all entries from this bag.
*
*  @post This bag contains no items (thus the count is 0). */
virtual void clear() = 0;

/** Counts the number of times a given entry appears in bag.
*
*  @param anEntry The value of the entry to be counted.
*
*  @return The number of times anEntry appears in this bag. */
virtual int getFrequencyOf(const ItemType& anEntry) const = 0;

/** Tests whether this bag contains a given entry.
*
*  @param anEntry The value of the entry to locate.
*
*  @return True if this bag contains anEntry, or false
*          otherwise. */
virtual bool contains(const ItemType& anEntry) const = 0;

/** Converts this bag into a vector.
*
*  @return A vector containing all the entries in this bag. */
virtual std::vector<ItemType> toVector() const = 0;
};

#endif


ReceiptArrayBag.h:

/** @file ReceiptArrayBag.h
*
*/

#ifndef RECEIPT_ARRAY_BAG
#define RECEIPT_ARRAY_BAG

#include "ReceiptBagInterface.h"

/** @class ReceiptArrayBag ReceiptArrayBag.h "ReceiptArrayBag.h"
*
*  Specification of an array-based ADT bag. */
template <typename ItemType>
class ReceiptArrayBag : public ReceiptBagInterface<ItemType> {
private:
/** Maximum capacity of this bag. */
static const int DEFAULT_CAPACITY = 6;

/** Number of items in this bag. */
int itemCount;

/** Maximum capacity of this bag. */
int maxItems;

/** Data storage. */
ItemType *items = new ItemType[DEFAULT_CAPACITY];

/** Parallel array for data storage*/
bool *inUse = new bool[DEFAULT_CAPACITY];

/** Gets the index of target in the array 'items' in this bag.
*
* @param target The ItemType value to retrieve the index of.
*
* @return The index of the element in the array 'items' that
*         contains 'target' or -1 if the array does not contain
*         'target'. */
int getIndexOf(const ItemType& target) const;

public:
/** Default constructor. */
ReceiptArrayBag();
int getMaxItems() const;
int getCurrentSize() const;
bool isEmpty() const;
bool remove(const size_t& receipt);
void clear();
int getFrequencyOf(const ItemType& anEntry) const;
bool contains(const ItemType& anEntry) const;
std::vector<ItemType> toVector() const;
};

#include "ReceiptArrayBag.cpp"

#endif


ReceiptArrayBag.cpp:

/** @file ReceiptArrayBag.cpp
*
*  @course CS1521
*  @section 1
*
*  Implementation file for the class ReceiptArrayBag.
*/

#include <cstring>

template <typename ItemType>
ReceiptArrayBag<ItemType>::ReceiptArrayBag()
: itemCount(0), maxItems(DEFAULT_CAPACITY) {}

template<typename ItemType>
int ReceiptArrayBag<ItemType>::getMaxItems() const
{
return maxItems;
}

template <typename ItemType>
int ReceiptArrayBag<ItemType>::getCurrentSize() const
{
return itemCount;
}

template <typename ItemType>
bool ReceiptArrayBag<ItemType>::isEmpty() const
{
return 0 == itemCount;
}

template <typename ItemType>
{
bool hasRoomToAdd = itemCount < maxItems;

{
ItemType *newArr = new ItemType[maxItems * 2];
std::copy(items, items + maxItems, newArr);
delete [] items;
items = newArr;
maxItems *= 2;
}

for (size_t i = 0; i < maxItems; ++i)
{
if (!inUse[i])
{
items[itemCount] = newEntry;
inUse[itemCount] = true;
return itemCount++;
}
}

// should theoretically never get here
return -1;
}

template <typename ItemType>
bool ReceiptArrayBag<ItemType>::remove(const size_t& receipt)
{
if(inUse[receipt])
{
--itemCount;
items[receipt] = ItemType{};
inUse[receipt] = false;
return true;
}
else return false;
}

template <typename ItemType>
void ReceiptArrayBag<ItemType>::clear()
{
itemCount = 0;
}

template <typename ItemType>
bool ReceiptArrayBag<ItemType>::contains(const ItemType& anEntry) const
{
bool found = false;

for (int i = 0; !found && i < itemCount; ++i)
{
if (anEntry == items[i]) found = true;
}
return found;
}

template <typename ItemType>
int ReceiptArrayBag<ItemType>::getFrequencyOf(const ItemType& anEntry) const
{
int frequency = 0;

for (size_t i = 0; i < itemCount; ++i)
{
if (inUse[i] && items[i] == anEntry) ++frequency;
}
return frequency;
}

template <typename ItemType>
std::vector<ItemType> ReceiptArrayBag<ItemType>::toVector() const {

std::vector<ItemType> bagContents;

for (int i = 0; i < itemCount; ++i)
{
bagContents.push_back(items[i]);
}
return bagContents;
}

template <typename ItemType>
int ReceiptArrayBag<ItemType>::getIndexOf(const ItemType& target) const {

bool found = false;
int result = -1;

for (int i = 0; !found && i < itemCount;)
{
if (items[i] == target)
{
found = true;
result = i;
}
else ++i;
}
return result;
}


main.cpp:

/** @file main.cpp
*
*  @course CS1521
*  @section 1
*
*  Testing the ReceiptArrayBag class.
*/

#include <cassert>
#include <iostream>
#include <string>
#include <cstdlib>
#include "ReceiptArrayBag.h"

void displayBag(ReceiptArrayBag<std::string>& bag)
{
std::cout << "The bag contains " << bag.getCurrentSize() << " items:" << std::endl;

std::vector<std::string> bagItems = bag.toVector();
int numberOfEntries = (int)bagItems.size();

for (int i = 0; i < numberOfEntries; ++i)
{
std::cout << bagItems[i] << " ";
}
std::cout << std::endl;
}

void bagTester(ReceiptArrayBag<std::string>& bag)
{
assert(1 == bag.isEmpty());
displayBag(bag);

std::string items[] = {"one", "two", "three", "four", "five", "one"};

std::cout << "Adding 6 items to the bag" << std::endl;
size_t *receipts = new size_t[bag.getMaxItems() * 2];
for (int i = 0; i < bag.getMaxItems(); ++i)
{
}
displayBag(bag);

assert(0 == bag.isEmpty());
assert(6 == bag.getCurrentSize());
assert(1 == bag.contains("three"));
assert(0 == bag.contains("ten"));
assert(2 == bag.getFrequencyOf("one"));
assert(1 == bag.remove(receipts[5]));
assert(1 == bag.getFrequencyOf("one"));
assert(1 == bag.remove(receipts[0]));
assert(0 == bag.remove(receipts[0]));
assert(0 == bag.getFrequencyOf("one"));

std::cout << "After clearing the bag: " << std::endl;

bag.clear();
displayBag(bag);

assert(1 == bag.isEmpty());
delete [] receipts;
}

int main()
{
ReceiptArrayBag<std::string> bag;

std::cout << "Testing the Receipt-Based Bag:" << std::endl;
bagTester(bag);
std::cout << "All done!" << std::endl;
}

• Is the "ReceiptBagInterface" template required by your class? – T.C. Feb 16 '15 at 14:57
• I think you should define a type for the receipt values. Your add mechanism returns a plain int but your remove takes a size_t, which is not very consistent. – Jonathan Leffler Feb 16 '15 at 15:20

You've committed a cardinal C++ sin and forgotten to implement a proper destructor - your class will always leak memory.

Remember: each new needs a corresponding delete (or new[] and delete[], as in this case) (I know that this is just an oversight on your part as you've remember to do it correctly in add, but it is a big one!).

Further, this will silently do the wrong thing for operator= and its copy constructor. You should either implement these or disable them:

ReceiptArrayBag(const ReceiptArrayBag&) = delete;
ReceiptArrayBag& operator=(const ReceiptArrayBag&) = delete;


The code in add does everything in the correct order, which is good. Always allocate, copy, and then delete, as if either of the first two throw an exception, it will leave everything in a consistent state (these are know as exception guarantees).

### 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.

• You can't "null out" removed items; each item in the array is an object, not a pointer, and can't be set to nullptr. The best you could do is set it to a default-constructed object, but there is little point in doing this. – Yuushi Feb 16 '15 at 14:08
• Thanks @Yuushi, you're absolutely right, I rewrote that paragraph. – janos Feb 16 '15 at 14:57
• I agree with almost all of your advice, except the first one about SRP: The combination of allocation+add is idiomatic for C++ containers, it makes a lot of sense for classes where the raw indices are not public anyway (unlike e.g. vectors), and your proposed redesign is error prone (what if the client forgets to call ensureCapacity, or passes too low a value?). – microtherion Feb 16 '15 at 17:32
• @microtherion I didn't meant that clients should call ensureCapacity before calling add. That should be done from add, by calling ensureCapacity with an appropriate target size. By replacing the implementation of allocation with a method call, add will no longer violate SRP. – janos Feb 21 '15 at 15:50
• inUse and items should be std::vector. This would save you all explicit memory management, and would fix the destructor and assignment issues noted by @yuushi.
• The block after if (!inUse[i]) in the add method sets item itemCount and returns itemCount. This is incorrect. It should be working on item i and returning i instead.

The thing that I find most disconcerting is this line in ReceiptArrayBag.hpp:

#include "ReceiptArrayBag.cpp"


Those are not typos on my part. You really did include a CPP file in the corresponding HPP file rather than the other way around. This would confuse anyone trying to modify your program later; even if it were only a momentary confusion, it's completely unnecessary.

As far as I can tell, functions such as contains() and getFrequencyOf() exist solely for the purpose of testing. But if you remove() an item that turns out to be "one", then (operationally speaking) contains("one") was true prior to the remove(). So it is redundant to test for contains("one") at that time. And if you call remove() three times and get items that all turn out to be "one", then 3 == getFrequencyOf("one") was operationally true prior to that sequence of calls. And in terms of the correctness of your implementation, I would argue that this is the only kind of thing that matters. You really should be verifying that you can correctly remove() all the items that are supposed to be in your bag; the tests of the internal state of the bag in between add() and remove() functions don't have much useful to say.

As far as I can tell, getIndexOf() isn't used at all, even for testing. Indeed it seems like a really bad idea to expose this level of detail of how the items in the bag are stored.

This snippet of code looks just plain wrong:

    if (!inUse[i])
{
items[itemCount] = newEntry;
inUse[itemCount] = true;


This basically says that new items always get added at the end of the array, even if there is an unused location at a lower address. I think what you had in mind here requires all three of these subscripts to be i.

You did not test whether the receipts of removed items are ever reused (as the requirements say they should be). Your test suite needs to have (at least once) a remove() followed by an add() in order to test that feature.

The algorithm for finding the next available location for an add() is OK for small or moderate-sized bags, but executing a long sequence of adds with no removes will take time O(n^2). There are ways to make the "find the next open location" an O(1) operation instead of worst-case O(n). You could implement a "list of freed nodes" using another auxiliary array, for example; there are at least two ways to do that, one using a "linked list" idea (but not necessarily literally using pointers), and one using a kind of stack.

On the plus side, you did well to double the size of the array when you need more space. You'd be surprised how many otherwise intelligent programmers don't think to do that when they write their first dynamically-sized array.

I dislike functions like toVector() whose purpose is just to make a temporary copy of the data structure that can be scanned for some purpose (in this case, to print it). I tend to try to implement some kind of iterator instead. But that's a matter of taste and it's probably not worth the effort in this case.