CSCI 159 Lab 6 (Nov. 25th/27th)

CSCI 159 Lab 6 exercises

Lab 6 is almost a two-week lab: it is due by 11:59:59pm Friday Dec. 5th

There are again two halves, a warm-up exercise working with structs and arrays of structs (warm-up exercise done in basic.cpp) and a design/implementation exercise (done in lab6.cpp):

the basic/warmup exercise (basic.cpp), worth 6 marks
the main design/implementation exercise (lab6.cpp), worth 12 marks
both parts are due by 11:59:59pm on Friday Dec. 5th

Here is the collection of new C++ syntax elements we'll be using for lab6.

Follow our usual setup process

Log in, open a browser, go to the lab6 page, open a terminal window:
(see lab 2 if you need a refresher on any of the steps)
get lab 6:
make -f make159 csci159/lab6
Go into your lab6 directory and begin the edit/compile/test/submit routine:
- to edit basic.cpp: pluma basic.cpp &
- to compile basic.cpp: make basicx
- to test basicx: ./basicx
- to submit: make submit
  once we get to the second half of today's lab:
- to edit lab6.cpp: pluma lab6.cpp &
- to compile lab6.cpp to create lab6x: make lab6x
- to test lab6x: ./lab6x
- to submit: make submit
As with previous labs, you'll see that the two .cpp files are nearly empty to start with.

First half: structs and arrays of structs (to be done in basic.cpp)

This program is going to allow the user to provide information for up to twenty circles and then it will display all pairs of circles that overlap (handy for collision detection when doing games or simulations).

For each circle they'll provide its radius and the x,y coordinates of its centre.

We'll use a struct to define a new 'Circle' datatype (with fields for x, y, and the radius) and the main routine will maintain an array of these circles to hold the actual data.

We'll use a suite of functions:

Basic structure

Our usual first steps will be to set up the #includes (for iostream, string, and cmath), any 'using std::whatevers', constants (including one for the maximum number of circles the program can handle), and function prototypes, but now we also need to put our struct type definition above the prototypes.

// specify the  maximum number of circles the program is capable of handling
const int MaxCircles = 20;

struct Circle {
   double x,y;  // (x,y) coords for the centre of the circle
   double rad;  // radius of the circle (must be > 0)
};

// get the desired number of circles from the user, 1..max
int getNumCircs(int max);

// get a real number from the user, optionally restricted to positive numbers only
double getNumber(string promptInfo, bool mustBePositive = false);

// fill all the fields of the circle struct (uses getNum for each)
void fill(Circle& c);

// fill all the circles (using the fill function)
void fillAll(Circle circs[], int num);

// see if two circles overlap
bool overlap(Circle c1, Circle c2);

// print one circle's information as (x,y:r)
void print(Circle c);

// print a list of all overlapping circles
void printOverlaps(Circle circs[], int numCircs);

The main routine can be kept fairly simple, doing just the variable declarations and calls to the core functions:

int main()
{
   // array of maximum number of circles
   Circle circles[MaxCircles];

   // find out how many the user actually wants
   int numberCircles = getNumCircs(MaxCircles);

   // fill the circles
   fillAll(circles, numberCircles);

   // display all the overlaps
   printOverlaps(circles, numberCircles);
}

In the remaining sections we'll cover the implementations of the functions themselves.

Numeric I/O and error handling

I'm certain you can all handle creating basic numeric input/error checking functions by now, so below I've provided sample versions. You are welcome to use your own, but the data values you get from the user must be in the same order as shown below: no extra questions, no changes in order. (First the number of circles, then for each circle its x coord then its y coord then its radius).

(Now that the programs are getting more complex and involve more data, a standardized batch of tests gets run on all student programs in addition to me reading your code. The test program provides fixed sets of test values in fixed orders, following the patterns in the code design below. If your program expects different information or in a different order then it won't work and will fail the testing.)

We'll use one function to get the number of circles from the user, between 1 and whatever maximum limit main decided to pass. (In this case main will pass our max constant, but having the value as a parameter will make the function more flexible/reusable.)

We'll use a second function to get numbers from the user, with an optional parameter specifying the number must be greater than zero (so we can use the same getNumber function for the radius as well as the x/y coordinates). This function also includes a string parameter that allows some customization of the prompt for the user.

Both of our functions will repeat until valid values are provided. (They repeat recursively here, feel free to use a loop if you prefer.)

// get the desired number of circles from the user, 1..max
int getNumCircs(int max)
{
   // get the number of circles from the user
   int numCs;
   cout << "Please enter the desired number of circles, 1.." << max << ": ";
   cin >> numCs;

   // error check and recurse if needed
   if (cin.fail()) {
      cin.clear();
      cin.ignore(LineLen, '\n');
      cerr << "The value must be an integer, please try again" << endl;
      numCs = getNumCircs(max);
   } else if ((numCs < 1) || (numCs > max)) {
      cerr << "The value must be in the range 1.. " << max << ", please try again" << endl;
      numCs = getNumCircs(max);
   }

   // return the validated result
   return numCs;
}

// get a real number from the user, optionally restricted to positive numbers only
double getNumber(string promptInfo, bool mustBePositive)
{
   // prompt the user, adjusting for the must-be-positive restriction if needed
   cout << "Please enter a number";
   if (mustBePositive) {
      cout << " greater than zero";
   }
   cout << " for the " << promptInfo << ": ";

   // get the user's input
   double num;
   cin >> num;

   // error check and recurse if needed
   if (cin.fail()) {
      cin.clear();
      cin.ignore(LineLen, '\n');
      cerr << "The value must be a number, please try again" << endl;
      num = getNumber(promptInfo, mustBePositive);
   } else if (mustBePositive && (num <= 0)) {
      cerr << "The value must be greater than 0, please try again" << endl;
      num = getNumber(promptInfo, mustBePositive);
   }

   // return the validated result
   return num;
}

Filling the circles

We'll use one function to fill in each field of a single circle (calling our getNumber from above), and a second function that fills in the entire array (calling the simpler function once on each element).

Since we've written the getNumber function, our basic fill function is very simple:

// fill all the fields of the circle struct (uses getNum for each)
void fill(Circle& c)
{
   c.x = getNumber("x coord");
   c.y = getNumber("y coord");
   c.rad = getNumber("radius", true);
}

The fillAll is also pretty straight-forward, simply loop through the array of circles one element at a time and call fill on each of them:

// fill all the circles (using the fill function)
void fillAll(Circle circs[], int num)
{
   // for each of positions 0 through num-1,
   //     call fill on circs[c]
}

Detecting the overlaps

We can detect if two circles overlap by computing how far apart their centres are then determining if this is greater than their combined radii.

We'll have one function to check a pair of circles to see if they overlap, and call this on each possible pair of circles.

I've provided the print and overlap functions, but left the printOverlaps as a commented exercise.

// see if two circles overlap
bool overlap(Circle c1, Circle c2)
{
   // calculate the distance between the two centres
   double xdist = c1.x - c2.x;
   double ydist = c1.y - c2.y;
   double distance = sqrt(xdist*xdist + ydist*ydist);

   // if the distance is more than the combined radii then they do not overlap
   if (distance > (c1.rad + c2.rad)) {
      return false;
   }

   // otherwise they overlap (or at least touch)
   return true;
}

// print one circle's information as (x,y:r)
void print(Circle c)
{
   cout << "(" << c.x << "," << c.y << ":" << c.rad << ")";
}

// print a list of all overlapping circles
void printOverlaps(Circle circs[], int numCircs)
{
   // we'll need a variable to track how many overlaps we've detected, initialized to 0

   // we'll use nested for loops that compares each circle with every circle later in the list
   //    (to avoid printing overlapping pairs twice)
   // for c1 is 0 to numCircs-2
   //     for c2 is c1+1 to numCircs-1
   //         call overlap on circs[c1] and circs[c2], and if it
   //            says they overlap then print the two of them
   //            (and increment our overlap counter)
}

A sample run

Below we show a sample run with three circles (a unit circle at the origin and two that overlap it).

Please enter the desired number of circles, 1..20: 3 

Now filling circle number 0 
Please enter a number for the x coord: 1 
Please enter a number for the y coord: 1 
Please enter a number greater than zero for the radius: 1 

Now filling circle number 1 
Please enter a number for the x coord: -1.5 
Please enter a number for the y coord: 0.99 
Please enter a number greater than zero for the radius: 0.85 

Now filling circle number 2 
Please enter a number for the x coord: 0 
Please enter a number for the y coord: 0.1 
Please enter a number greater than zero for the radius: 0.99 
 
Detecting overlapping circles... 
Overlapping pair: (1,1:1) and (0,0.1:0.99) 
Overlapping pair: (-1.5,0.99:0.85) and (0,0.1:0.99) 
Number of overlaps detected: 2

Second half: design and implementation problem (to be done in lab6.cpp)

For the main portion of lab6, you'll be implementing a program to maintain a queue of package delivery requests. As the user runs the program, they can:

Add new packages to the back of the queue, specifying the sender, receiver, address, contents, and the value of the package
Remove the front package from the queue and have its data displayed
Look up how many packages are currently in the queue
Print all the packages currently in the queue (from the front of the queue to the back of the queue).
Get a list of available commands (help)
Quit the program

Command handling

The interactions with the user (getting and processing commands, constants for the various commands, etc) are provided through a main routine and several more functions (implementations for these are already provided in lab6.cpp):

// constants representing the valid package commands
const char Help = 'H';   // command for displaying help menu
const char Quit = 'Q';   // command for quitting the program
const char Insert = 'I'; // command to get package info from the user and insert into the queue
const char Remove = 'R'; // command to remove a package from the queue and display its info
const char Size = 'S';   // command to display the current number of packages in the queue
const char Print = 'P';  // command to print the information for all packages in the queue
                         // (starting from front of queue and continuing to the back)
const char Error = 'E';  // used to represent any invalid commands

// display the available processing commands
void commandHelp();

// get a valid package command from the user
// (repeats until a valid command is provided)
char getCommand();

// command to process a command, applying it to the given queue
void processCommand(char command, Queue &Q);

// ====================================================================================
// ========== main routine ==========================================================
// ====================================================================================
int main()
{
   // set up a queue of packages
   Queue pkgs;
   initQ(pkgs);

   // introduce the user to the program and display the instructions
   cout << "\nWelcome to the package processor!\n";
   commandHelp();

   // keep processing commands until the user decides to quit
   char command;
   do {
      command = getCommand();
      processCommand(command, pkgs);
   } while (command != Quit);

   return 0;
}

Packages

The information for individual packages is contained in a Packages struct (already provided), with two functions that work on packages.

Skeletal versions of the fill and printPkg functions are provided, but you'll need to complete them. These are essentially just doing the I/O with the user and either filling or displaying the contents of a package.

// datatype describing a package for delivery
struct Package {
   string sender; // name of sender
   string recipient; // name of receiver
   string content; // description of package contents
   string address; // full address of receiver
   float value; // estimated value of contents
};

// fill package p with user-supplied data
void fillPkg(Package &p);

// display package p's information
void printPkg(Package p);

Your I/O wording doesn't need to exactly match the sample output, but make sure you ask your questions in the same order, to ensure that your lab6x will be compatible with the way the test scripts feed data into your program during testing.

First ask for the sender name
Then the receiver name
Then the address
Then the content description
Then the value
For each of the text fields the user can enter an entire line of text, including spaces/tabs, so use something like getline to obtain the content from them.

Queues

The information for the overall queue is contained in a Queue struct (already provided), with a number of functions to be implemented that work on queues, outlined in the code segment below.

For queues in general, the idea is that new incoming items are added to the back of the queue and items get removed from the front of the queue. In our implementation:

We're using an array to hold all the items currently in the queue, and will use fields front and back to keep track of the array position of the first and last current items in the queue.
We increment front after we remove an item and increment back as part of adding a new item.
Problem: eventually back reaches the end of the array, but the array might not be full if we've already done some removes from the front (so there are empty spaces at the front of the array).
Solution: when back is about to go off the end of the array we set it to 0, so the queue 'wraps around' to the array beginning again. Of course, we have to make sure the array isn't actually full (or we're overwrite valid content at the front of the queue), so we'll also keep track of the number of packages in the queue (using the size field), and reject attempts to insert new things into a full queue.
New problem: as we keep doing removes, front can eventually reach the end of the array and will need to wrap-around to the beginning of the array in the same fashion as back did. We can also use size as a way to check for invalid removes: if the current number of packages in the queue is 0 then no remove is possible.
Printing: if we want to print the current collection of packages from the front of the queue to the back of the queue we now need to start at front and increment one position at a time until we reach the back, wrapping around to 0 if we're about to go off the end of the array.
Resets when the queue is emptied: Just to minimize the number of times wrap-around actually occurs, anytime the queue size hits 0 (i.e. after a remove) we'll reset front and back to -1 and size to 0.

// maximum number of packages we can be processing at once
const int MaxPackages = 4;

// datatype describing a queue of packages, implemented as a circular buffer
// (an array with tracked front and back positions, with the potential for front
//   and back to 'wrap-around' as items are inserted and removed over time)
struct Queue {
    Package pkgArray[MaxPackages]; // actual array of packages
    int front; // position of front package in queue (-1 if empty)
    int back; // position of back package in queue (-1 if empty)
    int size; // number of elements currently in the queue (0 if empty)
};

// initialize a package queue (as empty)
void initQ(Queue &q);

// looks up and returns the number of elements currently in queue q
int getSizeQ(Queue q);

// adds new package to the back of queue q, copying its values from p
// returns true if successful, false otherwise
//    (can fail if the queue is full)
bool insertQ(Package p, Queue &q);

// removes front package from queue q, copies data into p
// returns true if successful, false otherwise
//    (can fail if the queue is empty)
bool removeQ(Package &p, Queue &q);

// displays the information about each package in the queue
void printQ(Queue q);

The technique we're using is called a circular buffer, and is widely used for array-based queue implementations.
The starter code for functions insertQ, removeQ, and printQ contains suggested algorithms that will handle the wrap around correctly (as well as the error checking for invalid inserts/removes).

Overall starter code

As discussed above, much of the program code is already provided in your lab6.cpp file, with a handful of Package and Queue functions left for you to finish, and recommended algorithms for each of the Queue functions that have to cope with 'wrap-around'.

You can also see a copy of the lab6.cpp starter code here.

Sample Run

Below we show a sample run, including some examples of the error handling and (assuming MaxPackages is set to 4) tests the logic for the queue 'wrapping around'. (User input is shown in bold italics for greater clarity.)

Welcome to the package processor! 
The available commands are: 
   H to display this help menu 
   Q to exit the program 
   I to add a new package to the back of the queue 
   R to remove and display the front queue package 
   S to see the number of packages currently queued 
   P to show each of the packages currently queued 
 
Enter a command (HQIRSP): S
The current number of queued packages is 0 
 
Enter a command (HQIRSP): P
The queue is currently empty 
 
 
Enter a command (HQIRSP): R
Error: attempt to remove package into from an empty queue 
Removal failure 
 
Enter a command (HQIRSP): I
Enter sender name (one line): its me
Enter receiver name (one line): them folks
Enter destination address (one line): 1234 over therre
Enter content description (one line): just some stuff, 1 or 2 things
Enter content dollar value, e.g. 20.99: 99.23
Insertion successful 
 
Enter a command (HQIRSP):  I 
Enter sender name (one line):  them 
Enter receiver name (one line):  me 
Enter destination address (one line):  here 
Enter content description (one line):  garbage 
Enter content dollar value, e.g. 20.99:  0.01 
Insertion successful 
 
Enter a command (HQIRSP): I
Enter sender name (one line): someone
Enter receiver name (one line): someone else
Enter destination address (one line): someplace, I dunno
Enter content description (one line): whatever
Enter content dollar value, e.g. 20.99: 1.23
Insertion successful 
 
Enter a command (HQIRSP): P
The queue contents (front to back) are: 
To:      its me 
Addr:    1234 over therre 
From:    them folks 
Content: just some stuff, 1 or 2 things 
Value:   99.23 
 
To:      them 
Addr:    here 
From:    me 
Content: garbage 
Value:   0.01 
 
To:      someone 
Addr:    someplace, I dunno 
From:    someone else 
Content: whatever 
Value:   1.23 
 
 
Enter a command (HQIRSP): R
Successful removal of package: 
To:      its me 
Addr:    1234 over therre 
From:    them folks 
Content: just some stuff, 1 or 2 things 
Value:   99.23 
 
 
Enter a command (HQIRSP): P
The queue contents (front to back) are: 
To:      them 
Addr:    here 
From:    me 
Content: garbage 
Value:   0.01 
 
To:      someone 
Addr:    someplace, I dunno 
From:    someone else 
Content: whatever 
Value:   1.23 
 
 
Enter a command (HQIRSP): S
The current number of queued packages is 2 
 
Enter a command (HQIRSP): I
Enter sender name (one line): them again
Enter receiver name (one line): me again
Enter destination address (one line): this place
Enter content description (one line): more stuff
Enter content dollar value, e.g. 20.99: 100
Insertion successful 
 
Enter a command (HQIRSP): I
Enter sender name (one line): me2
Enter receiver name (one line): them2
Enter destination address (one line): there2
Enter content description (one line): stuff2
Enter content dollar value, e.g. 20.99: 1.234
Insertion successful 
 
Enter a command (HQIRSP): S
The current number of queued packages is 4 
 
Enter a command (HQIRSP): P
The queue contents (front to back) are: 
To:      them 
Addr:    here 
From:    me 
Content: garbage 
Value:   0.01 
 
To:      someone 
Addr:    someplace, I dunno 
From:    someone else 
Content: whatever 
Value:   1.23 
 
To:      them again 
Addr:    this place 
From:    me again 
Content: more stuff 
Value:   100 
 
To:      me2 
Addr:    there2 
From:    them2 
Content: stuff2 
Value:   1.234 
 
 
Enter a command (HQIRSP): R
Successful removal of package: 
To:      them 
Addr:    here 
From:    me 
Content: garbage 
Value:   0.01 
 
 
Enter a command (HQIRSP): R
Successful removal of package: 
To:      someone 
Addr:    someplace, I dunno 
From:    someone else 
Content: whatever 
Value:   1.23 
 
 
Enter a command (HQIRSP): R
Successful removal of package: 
To:      them again 
Addr:    this place 
From:    me again 
Content: more stuff 
Value:   100 
 
 
Enter a command (HQIRSP): R
Successful removal of package: 
To:      me2 
Addr:    there2 
From:    them2 
Content: stuff2 
Value:   1.234 
 
 
Enter a command (HQIRSP): S
The current number of queued packages is 0 
 
Enter a command (HQIRSP): P
The queue is currently empty 
 
 
Enter a command (HQIRSP): X
Error: X is not a valid option, please try again 
 
Enter a command (HQIRSP): R
Error: attempt to remove package into from an empty queue 
Removal failure 
 
Enter a command (HQIRSP): I
Enter sender name (one line): 1
Enter receiver name (one line): 2
Enter destination address (one line): 3
Enter content description (one line): 4
Enter content dollar value, e.g. 20.99: foo
Error: that was not a numeric value, please try again 
Enter content dollar value, e.g. 20.99: ick
Error: that was not a numeric value, please try again 
Enter content dollar value, e.g. 20.99: -1
Error: the value cannot be negative, please try again 
Enter content dollar value, e.g. 20.99: 5
Insertion successful 
 
Enter a command (HQIRSP): P
The queue contents (front to back) are: 
To:      1 
Addr:    3 
From:    2 
Content: 4 
Value:   5 
 
 
Enter a command (HQIRSP): Q
 
Bye!