Array, Vector and Pointer Exercises Home Class Info Links Lectures Newsgroup Assignments

Below are exercises suitable for submission to the Code Critic after reading Chapters 1 through 7, and Chapter 19, of the textbook. Don't forget the rules of the queue.

The exercises are:

## Exercise: Seat Assignment

Exercise 7.20 describes a simple seat assignment problem. As described, it's not set up for test-driven development, and is vague about things such as

• how seats are assigned -- randomly, in order?
• what should happen if a section is full -- return failure (how?), move to other section?

So, here's an API (application program interface) designed for testing. Define a class `ReservationManager` with these public member functions:

• a constructor `ReservationManager(int firstClass, int coach)` that takes the number of seats in first class and the number of seats in coach
• `int assign(int seatType, int customerID)` should take a seat type (1 or 2) and a customer ID (any positive integer) and return an assigned seat number (one-based as in the book), or 0 if no seat is available in the requested section. Seats should be assigned in order.
• `int assignment(int customerID)` should take a customer ID and return the assigned seat number, or 0 if the customer has no seat assignment.

If `assign()` is called for a customer already assigned a seat, the previously assigned seat should be returned.

For example, tests for the example in the exercise might look like this:

```ReservationManager mgr(5, 5);
CPPUNIT_ASSERT_EQUAL(1, mgr.assign(1, 100));
CPPUNIT_ASSERT_EQUAL(6, mgr.assign(2, 101));
CPPUNIT_ASSERT_EQUAL(7, mgr.assign(2, 102));
CPPUNIT_ASSERT_EQUAL(2, mgr.assign(1, 103));```

There should also be calls to `assignment()` to verify the assignments have been saved.

Start simple! Develop tests for a small plane with no first class seats, and no calls to `assign()` with the same customer ID twice. Write the tests, run them to show failure, then develop code to pass those tests.

After those tests are passed, add some tests for the repeated customer case. Run the tests. Make sure you see the failures you expect. Then write the code to handle this case.

After those tests are passed, write more tests for a plane with some first class seats. Run the tests. Make sure you see the failures you expect. Then write the code to handle first class seating.

Create a separate test function for each plane configuration and request sequence, e.g., you might have one function for the case where first class is filled (and over-requested) first, before coach, another function where the opposite happens, and a third where the requests are interleaved.

Think about ways you can use `for` loops to short the length of the test code.

Instead of storing 0 and 1 in the seating chart, as described in the book, store the customer ID. You can assume the ID is never 0.

Submit to Code Critic:

• First submit just your test code file.
• After your tests have been approved, and your code passes the approved tests, submit your `.h` and `.cpp` file that implements your reservation manager.

Remember to put a header comment at the start of the files that identifies what file they are.

### Wrap Up

When the above has been approved via the Code Critic, run make handin.

Email the Zip archive produced by your Makefile with the Subject EECS 211: Seat Assignment.

### Background

The textbook uses arrays to store grades (Section 7.6). While OK as a demonstration of arrays, this is actually a terrible way to do grades. Notice that the number of grades is fixed as 10 for all courses (Fig. 7.16). How useless is that?

The solution in C++ for storing data whose number you don't know in advance is to use vectors. The book talks about them in Section 7.11, but treats them exactly like arrays, which misses the key point of vectors: vectors are dynamic -- they grow automatically as data is added.

To do this, you call the vector member function `push_back()`

```vector<int> grades;
cout << "There are " << grades.size() << " grades." << endl;
for ( int i = 0; i < grades.size(); ++i ) {
cout << (i + 1) << ": " << grades[i] << endl;
}```

Create a new project directory called `grades`. Extract your Zip archive for your previous GradeBook exercise into this directory, to get a clean copy of the old code. If you're using an IDE like Code::Blocks or XCode, create a new `grades` project.

Add to `GradeBookTests.cpp` tests for the following function:

• `int GradeBook::getGrade(int n)` should return the n'th grade, when `0 <= n < grades.size()`, and -1 otherwise.

You should have tests for getting grades when there no grades, and when `GradeBook::addGrade()` has been called.

Test your tests with your current GradeBook. Make sure the old tests pass but the new ones fail.

Then, update the relevant parts of `GradeBook.h` and `GradeBook.cpp` to use a vector of integers to store the grades.

Run your tests. If any fail, fix the code or the tests as appropriate.

If you haven't already, remove redundant code:

• Remove data members for the grade total or number of grades.
• Change the member function that used these data members to get or calculate their values from the vector.

Submit to Code Critic:

• The new or changed test code (not code that hasn't changed), your header code and your implementation code

Clearly label each section of code.

### Wrap Up

When the above has been approved via the Code Critic, run make handin.

## Exercise: Blob Counter

The Electro-Magic-Microscope company has hired you to develop a program that takes a B&W microscopic image and returns the number of "blobs" in the image, e.g., they might be bacteria or blood cells or whatever. A blob is a set of black pixels that border each other, horizontally, vertically or diagonally. A blob can be as small as one pixel or as large as the entire image.

Here's the kind of output they would like to see for two images, printed on a console, using x's for black pixels and periods for white, with a blob count. (The image data at the top will be explained later.)

As you can see, blobs can get pretty long.

Your job is to use TDD to implement a blob counter.

### Background

#### Representing images

Images on a computer are two-dimensional arrays of pixels, where each pixel is a set of bits, representing color information. For black and white images, just one bit is needed for each pixel -- black by convention is 1, white is 0.

Internally, a 2-dimensional array of boolean values makes the most sense for representing a small image. Externally however, such arrays are not easy to write down for testing. For 8 x 8 black and white images, a more compact external notation is hexadecimal numbers. Hexadecimal uses base 16, with the digits 0 through 9, followed by A (10), B (11), C (12), D (13), E (14), and F (15). If you've ever worked with HTML color codes, like #CC6633 (one form of brown), you've worked with hexadecimal numbers. Each hexadecimal digit maps to exactly 4 bits. Decimal digits don't do that. So for example, C (12) in binary is 1100, 6 is 0110, and 3 is 0011. So the color code #CC6633 is the 24 bit binary number 1100 1100 0110 0110 0011 0011.

In C++, you write numbers in hexadecimal notation by starting them with a "0x", e.g., `0xCC6633`.

An 8 x 8 image has 64 bits, or 16 hexadecimal digits. The image on the left above, with 3 blobs, could be represented in binary and hexadecimal thus:

`........`0000 000000
`xx......`1100 0000C0
`....xxx.`0000 11100E
`x..x....`1001 000090
`xx..x...`1100 1000C8
`........`0000 000000
`........`0000 000000
`........`0000 000000

On many C++ compilers, including Cygwin, 64 bits is too big for one unsigned long, so we'll use two, one for the upper half of the image and one for the lower half. Therefore, the image would be represented in C++, using the 0x numeric prefix for hexadecimal literals, as `0x00C00E90` and `0xC8000000`.

#### Counting blobs

At first it might seem that counting blobs could be very tricky, especially considering the image above on the right. Blobs can twist and turn so no simple left to right, top to bottom scan will work. But, if you have an array you can erase (and reset later!), then there's a clever solution that works quite nicely:

• Start scanning from left to right, top to bottom.
• If you find a pixel that's black, erase the entire blob that pixel is in, as described below, and add one to your count of blobs found.
• Continuing scanning from that point for the next black pixel.
• When you reach tne end of the array, you have the total count.

Erasing the blob is the key to this. It has to erase a blob, no matter how convoluted. A simple recursive algorithm will do it. You should work out the details but here's the essence:

Erase blob(pixel): If the pixel is black, set it to white, and for each neighboring pixel, call erase blob.

Watch out for infinite loops! Watch out for the edges of the image!

Use TDD, define the class `Image` with this API:

• the constructor `Image::Image( unsigned long u, unsigned long l )` takes two unsigned longs containing the upper and lower data bits for an image, as described above
• `int Image::getBlobCount( )` returns the number of blobs in the image
• `void Image::display( )` prints the output as shown in the examples above

You won't be able to test the display function with CppUnit, but it will be useful to call when a test of `getBlobCount()` fails. So define `display()` early, when you hit your first bug.

Hint: See Figure 15.8 for a simple way to print numbers in hexadecimal.

Start simple! What's the simplest possible case? An image with no blobs! So write a test for that, make sure it fails (or doesn't even compile), then do the simplest thing that could possibly work (DTSTTCPW). That's pretty easy for this case. Don't do anything more. This is a good chance to get all the files and prototypes right without worry about any algorithms. The main algorithms you'll need are:

• Loops to take the unsigned long data in the constructor and build an internal two-dimensional array of bool values to represent the image
• Loops to print that image when `display()` is called

Hint: you can use division and remainder to "peel" off the bits in the unsigned long data. No matter how you write a number, it's all binary inside the computer. But this will give you the bits from right to left, so be careful how you write your loops to fill up the internal array.

Since the image is blank (all zeros) no code is needed to count blobs yet.

Test to make sure the above parts are working.

What's the next simplest? How about 1 pixel blobs, somewhere in the image. Create test cases for that (some hexadecimal practice), make sure the tests fail, then add code to your constructor to set the blob counter. Something very simple should work when only single pixel blobs are involved. You'll need some loops to search the array for pixels.

Now what? One multi-pixel blob? Or multiple single pixel blobs? Your call. Both need to be done, but you decide which to tackle first.

When the above all work, you're finally ready tackle the general case of multiple multi-pixel blobs.

Submit to Code Critic: