CSCI 159 Lab 6 exercises

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

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):

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

Follow our usual setup process

  1. 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)

  2. get lab 6:
    make -f make159 csci159/lab6

  3. Go into your lab6 directory and begin the edit/compile/test/submit routine: 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).

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, the functionality from a user perspective is expected to be the same as lab5, but this time we'll store the container information in an array of structs rather than in one array of strings plus one array of floats.

We'll start by declaring a struct type to hold information for a single container, e.g. 
struct Container {
   string name;
   float size;
};
Our main routine will thus just need a single array (whose elements are of type Container), and our sorting function will just expect to be passed this one array.