SI204 Class 33: Simple Classes III

Homework
To appear Write a program that reads in a bunch of labeled points from a file like points.txt and a bunch of segments from a file like segments.txt, and then answers user questions like whether or not two segments have a common endpoint and whether or not two segments cross. For Example:
Command: commonendpoint A B
Answer : yes
Command: cross B C
Answer : yes
Command: cross A D
Answer : n
Command: quit
Use at least a class point and a class segment, which would contain two point objects.

Turn In a screen capture of your program running and a printout of your program.

Lecture
Let's look back at a problem we considered in Lecture 29. We have a file namedgrades.txt, which contains student grade information. The file looks like this:
11 students
10 homeworks
Adams	58	96	65	72	93	67	59	74	95	56
Brown	96	67	56	74	94	100	98	68	95	65
 .
 .
 . 
telling us initially how many students we have, how many homework scores, and then listing all the student names followed by their homework scores. Now, I'd like to simply read in this data, store it, and then answer user queries concerning the data. For an easy start, we'll just assume that the query will simply be a student name and we're supposed to give the homework average.

Now, assuming there are Ns students and Nh homeworks, the natural way for us to think of this is to say "I'd like to have an array of Ns objects of type Student." We know how to construct a class Student, so that't no problem, but what data members would we need to store this student data? We'd need a string to store the name, and we'd need ... well, we'd need an array of Nh ints to store the homework grades. In other words, we'd need a data member of type int*.

class Sudent
{
public:
  string name;
  int *hw;
};
Now, packaged up this way, an object of type Student representing the student "Brown" from above would look like this:

Now, the question is, if S is the name of the Student object from the picture, what expression would give me the value of the homework assignment with index 2? Well, S.hw is the name of the pointer to the array of grades, so I just need to subscript it with a 2: S.hw[2]! I might be tempted at this point to look back at my original problem and say that I'll create my storage for all this student/grade data with:

  Student *stu = new Student[Ns];
It's true that stu is now an array containing Ns object of type Student, but remember that each Student object has data member hw, which is just an unititialized pointer at this juncture. We need to go back and allocate homework-grade arrays for each Student object in the array. So creating our storage really looks like this:
  Student *stu = new Student[Ns];
  for(int j = 0; j < Ns; j++)
    stu[j].hw = new int[Nh];
At this point, writing the program is not very new for us: Here's my solution. All I did was use the top-down design that we've seen so many times. I simply wrote the main function the way I wished I could, and created the classes and functions that made writing main that way possible.

Another look at sorting

Now let's up the ante a little bit by sorting out student records and printing them out in sorted order, rather than answering queries. In particular, let's sort them by their grades on homework assignment #4, so that the student with lowest grade on assignment #4 comes first, and the student with highest grade on assignement #4 comes last. We'll have our array stu of objects of type student, and we'll use the same old selection sort routine we've always been using. Now, at some point in selection sort, we'll swap two elements of stu and I want to take a brief moment to look at what that means. The following picture shows how swap(stu[i],stu[j]) affects things. Hopefully you see, once again, that we're not moving the actual arrays of grades at all, we're simply moving the pointers to those arrays.

Now, if we're going to sort this array of Student objects, it's just like sorting anything else!

void selectionsort(Student *A, int N)
{
  for(int length = N; length > 1; length--)
    swap(A[maxindex(A,length)],A[length-1]);
}
int maxindex(Student *A, int N)
{
  int imax = 0, i;
  for(i = 1; i < N; i++)
    if (before(A[imax],A[i]))
      imax = i;
  return imax;
}
void swap(Student &a, Student &b)
{
  Student temp = a;
  a = b;
  b = temp;
}

So, the only thing that remains is to produce a before function that will take two Student objects and decide whether the first needs to come before the second. Remember we want our Student objects in order from lowest to highest score on homework #4. So, for before(a,b), I need to determine whether the homework #4 score for a is less than the homework #4 score for b.

bool before(Student a, Student b)
{
  if (a.hw[4] < b.hw[4])
    return true;
  else
    return false;
}
With this, it's easy to write a program that prints out students & their HW#4 scores ordered from lowest to highest HW#4 score. Here's a complete program.

Letting the user choose which grade to sort on breaks our sort scheme!

Now, a better version of the above program would allow the user to choose which homework assignment we sorted on. So, if x is the assignment number, we'd have to modify before to be:
bool before(Student a, Student b)
{
  if (a.hw[x] < b.hw[x])
    return true;
  else
    return false;
}
However, there's a problem! Where does the before function get x from? The only way it can get x is if we pass it in as a parameter. So the function must look like:
bool before(Student a, Student b, int x)
{
  if (a.hw[x] < b.hw[x])
    return true;
  else
    return false;
}
Now, this fixes before, but it neccesitates a change in maxindex, which is the function that calls before.
int maxindex(Student *A, int N)
{
  int imax = 0, i;
  for(i = 1; i < N; i++)
    if (before(A[imax],A[i],x))
      imax = i;
  return imax;
}
Now maxindex has the same question --- where is it going to get x from? It seems that another parameter is required for maxindex as well.
int maxindex(Student *A, int N, int x)
{
  int imax = 0, i;
  for(i = 1; i < N; i++)
    if (before(A[imax],A[i],x))
      imax = i;
  return imax;
}
Similarly, sort is going to require an extra parameter to pass along to maxindex. Putting it all together, we get this final program. Pretty nice, eh?

Composition of classes

Let's consider a scenario in which we have data readings for another cockroach that give us a time in [hh:mm:ss] format, and a position in (x,y) coordinates. For example, trial.txt. We want the user to be able to enter a time in [hh:mm:ss] format and we tell him where the roach is (i.e. en route between which two points).

We've dealt with points before, and we will again, so let's go ahead and give the basic class definition & function prototypes for points:

//--- POINT ---------------------------------//
class point
{
public:
  double x, y;
};
void read(point &p, istream &IN);
void write(point p, ostream &OUT);
Now, while we may not have dealt with times in hh:mm:ss for a while, it is not unlikely we'll have to deal with such things again. Therefore, it is natural to give a class definition and some prototypes for an hhmmss class:
//--- TIME IN HH:MM:SS ----------------------//
class hhmmss
{
public:
  int h,m,s;
};
void read(hhmmss &T, istream &IN);
bool operator<(hhmmss a, hhmmss b);
Being a little adventurous, I'm living on the edge and defining the operator< for hhmmss objects. Might come in useful if I have to figure out what happened first! Now, a data reading consists of a time and a position, so it might be nice to have a datum class that records a single data reading. It'd look something like this
class datum
{
public:
  point position;
  hhmmss time;
};
... and I'd probably want a function void read(datum &D, istream &IN); to read in such objects. With all of this (and with all these functions defined!) writing my main function is not too difficult:
  // Read and store data readings
  datum *A = new datum[N];
  for(int i = 0; i < N; i++)
    read(A[i],IN);

  // Get the query time from the user
  hhmmss T;
  cout << "Enter a time: ";
  read(T,cin);

  // Find the first sighting at or after given time
  int k = 0; 
  while (k < N && A[k].time < T)
    k++;
Then it would just remain to write out the information to the user. Take a look at this complete program. There are several important things to look at here:

  1. I used bottom up design to solve this problem. I started off with the pieces (classes and functions) that I knew I could define easily, and that I knew would come in handy here and probably in other programs as well. Then I started to put these pieces together to create a program.

  2. My datum class contains as data members two other classes I defined --- point and hhmmss. This is called composition of data types. We've already been doing this, of course, in having data members that are of type string.

  3. Notice how I used operator overloading to define the < operator for objects of type hhmmss. This made the code in my main function easier to write.

  4. Notice how often function overloading comes up when you start defining classes --- I have three functions named read!

  5. Notice how I used short-circuit evaluation of boolean expressions in my while-loop. The program may well have crashed without the short-circuit feature!

Problems

  1. Build on the solution to the last problem, so that the data file does not need to be given in time-sorted order.

  2. Build on the solution to the last problem so that it gives the average velocity of the roach on the leg containing the time entered by the user.

Asst Prof Christopher Brown
Last modified: Tue Nov 12 18:05:48 EST 2002