20-CS-122-001 Computer Science II Spring 2012
Homework Assignment 4

Virtual functions, classes, inheritance, lists, queues, stacks, applications

Maintaining an Ordered List

Due: May 3, 2012 (submit instructions: here)


Rationale:

Class creation, and manipulation of arrays.

Homework Problem:

Write a C++ program that includes classes Job and Schedule as described below. These classes will be used in the next homework. The Job class is defined in the implementation requirements section below. Each object of class Job has positive integers called profit, deadline, and identity. The constructor of the Job class is

   Job (int id, int p, int d) { identity = id; profit = p; deadline = d; }

We are principally interested in deadlines and these are given as the third argument.

An object of class Schedule maintains an array, called schedule, of pointers to objects of class Job. The size of the array is passed as an argument to the constuctor of this class.

Implement a method, prototyped as

   bool insert(Job *job);

of class Schedule which is used to insert a reference to a Job object (pointed to by job in this case) into array schedule, making sure the following restriction is satisfied: for all 0 <= i, if there is a Job object referenced at schedule[i], it has a deadline no greater than i+1. If the restriction cannot be satisfied or if all the elements of the array are referencing Job objects, the insert method returns false without changing the array, otherwise the array is modified and insert returns true.

There are several ways to implement the insert method. The simplest and least efficient implementation maintains all objects in successive locations of schedule. An illustration of this is presented in this power point presentation. An improved implementation attempts to place jobs at their deadline. If that space in schedule is occupied, a search toward schedule[0] is undertaken for an unoccupied slot. When one is found, the job is placed there. This power point presentation illustrates the idea.

Important: Observe that it is OK for schedule[i] not to reference a Job object and for schedule[i+1] to reference a Job object. This means checking array references for deadlines in order of increasing array index does not necessarily stop when the first array element not referencing a Job object is encountered. To determine whether or not a Job object is referenced, initialize schedule with all its elements pointing to NULL and use a check for NULL during the insert operation.

A third, and most efficient method makes use of an auxilliary index array. This method is rather advanced. It is illustrated here (eager) and here (lazy) for those interested.

The << operator should be overloaded to display the identity, profit, and deadline of the Job objects referenced in schedule in increasing order of deadline. An example of this overloading, assuming the 2nd method of maintaining the schedule of Job objects, is given in the implementation requirements section below.

Here is an example of the use of the code you should write:

   Schedule *schedule = new Schedule(4);
   schedule->insert(new Job(0, 45, 3));
   schedule->insert(new Job(1, 15, 2));
   schedule->insert(new Job(2, 25, 1));
   schedule->insert(new Job(3, 35, 3));
   schedule->insert(new Job(4, 55, 5));
   schedule->insert(new Job(5, 56, 4));
   cout << schedule << "\n";

should output [2:25,1] [1:15,2] [0:45,3] [4:55,5] because 1) after jobs 0,1,2 are inserted, it is not possible to insert a job with deadline 3 without violating the insertion restriction; 2) once job 4 is inserted the array is full so job 5 cannot be inserted.

Requirements:

  1. Functional requirements:
    1. The program shall read a text file and display the results to the console.
    2. The input file shall be identified on the command line (that is, use int main(int argc, char **argv)).
    3. The input file shall contain printable ascii characters only plus newline characters for terminating a line.
    4. Each line of the input file shall contain a sequence of three positive integers, separated by blanks, corresponding to data applicable to a single job. The first of three numbers is the job identity, the second is the deadline (given as a positive integer), the third is the payoff.
    5. See dead.10.dat for an example input file. On this file your program should return a schedule involving 7 jobs with a total payoff of 8,278,215.

  2. Performance requirements:
    1. Time: Less than 1 second to read a 10000 object file such as dead.10000.dat on a hard drive of 20 MB/s throughput (profit: 8,018,113,802). Less than 1 second to solve a 10000 job input on a 1 GHz or faster i386 or compatible architecture.
    2. Space: Less than 2MB of RAM for 10000 objects.

  3. Implementation requirements:
    1. Use a Job class to organize all job information as follows:
      class Job {
      friend class Schedule;
      friend ostream & operator<<(ostream & out, Schedule & sched);
         int identity, deadline, profit;
      
       public:
         Job (int id, int p, int d) { identity = id; profit = p; deadline = d; }
      };
      

    2. Use a Schedule class to maintain an incrementally changing schedule of jobs:

      class Schedule {
      friend ostream & operator<<(ostream & out, Schedule & sched);
         Job **schedule;
         int njobs;         // identifies the number of jobs in the schedule
      
      public:
         // This part is changed to reflect method 2 for maintaining a schedule
         Schedule (int njobs) { schedule = new Job*[njobs]; this->njobs = njobs; }
      
         // The "insert" procedure checks jobs in the existing schedule,
         // which are assumed to all complete before their deadlines, in
         // index order until it finds the first place where the new job 
         // can be inserted without violating the insertion restriction
         // stated above, or until it determines this is not possible.  
         // If the input "job" can be added to the schedule, it is added 
         // and "insert" returns "true". Otherwise, the schedule is left 
         // untouched and "insert" returns "false".
         bool insert (Job *job);
      };
      

      The following is the overloaded << operator, assuming method 2 is used to maintain a schedule of Job objects.

      ostream & operator<<(ostream & out, Schedule & sched) {
         long long total=0;
         out << "Result: ([job:profit,deadline]...)\n";
         for (int k=0; k < sched.njobs ; k++) {
            if (sched.schedule[k] != NULL) {
               out << "[" << sched.schedule[k]->identity
                   << ":" << sched.schedule[k]->profit
                   << "," << sched.schedule[k]->deadline < "] ";
               total += sched.schedule[k]->profit;
            }
         }
         out << "\nTotal Profit: " << total << "\n";
         return out;
      }
      

    3. Use a function called countJobs to count the number of jobs in a specified data file:

      // Count the number of jobs in the file whose name is specified as "filename".
      // Returns a negative number if the file is not found.
      int countJobs (char *filename);
      

    4. Use a function called readData to read the data from a file:

      // Read in data from file called "filename" and insert items into 
      // the "Schedule" object referenced by "sch" in the order they are 
      // read from the file.  Assume the file contains all distinct jobs
      // (that is, it is possible that two jobs have the same deadline
      // and profit but they are still considered distinct).
      void readData(Schedule *sch, char *filename);
      

    5. The following main goes with the above:

      int main(int argc, char **argv) {
         if (argc != 2) {
            cerr << "\nUsage: " << argv[0] << " <filename>\n";
            exit(0);
         }
      
         int njobs = 0;   
         if ((njobs = countJobs(argv[1])) < 0) {
            cerr << "File not found: " << argv[1] << "\n"; 
            exit(0);
         }
      
         Schedule *sch = new Schedule(njobs);
         readData(sch, argv[1]);
         cout << *sch << "\n";
      }