Lab 7. Abstract data types. Implementation and testing

Lab 7. Abstract data types. Implementation and testing.

How to submit your code

Each program (the source code .cpp file) should be submitted through Blackboard (Course Materials > Lab).

You can submit all your programs at the end of the lab session in one submission. This way, we can hopefully avoid the situation when you are quickly writing your program, immediately uploading it to Blackboard, but then, say 10 minutes later, realizing that there is a bug in it.

Basically, submit when you are sure that it will be your final version.

Each program should start with a comment that contains your name and a short program description, for example:

  Author: Your Name 
  Description: Lab 1. Task 1. Hello world

You can submit incomplete programs, but their “incomplete” status must be clearly mentioned in the comment to the program. In this case, also briefly describe what is implemented, and what is not.

Scheduler - intro.

You work at a certain software development company, and the management is sure that the programmers are not used optimally. So, they devised a program to help scheduling when the programmers should work, and for how long.


Of course, they devised the thing, and you have to implement it.

24 time slots


The interface of the data type Scheduler

You are provided with the specification, what the scheduler is supposed to do. In addition to the specification, you are provided with a whole bunch of unit test that will test the functions you implement.

>>> Download full source code: adt.cpp <<<

The class declaration looks like this (the main function and the tests are not included here to keep it short):

// The employees at a certain software development company
enum Programmer {
    Alice=1, Bob=2, Carol=3, Dave=4, Eve=5, Frank=6, Grace=7, UNASSIGNED = 0

const int N = 24;
const int NOT_FOUND = -1;

class Scheduler {
    Programmer timetable[N];

      // Sets the schedule to UNASSIGNED for all time slots
    void init();

      // Returns who is assigned to work in the time slot t.
      // If t is out of bounds [0,N-1], return UNASSIGNED
    Programmer get(int t);

      // Assigns the programmer to the time interval if the entire interval is vacant.
      // The interval must have positive duration (duration > 0).
      // Returns true if succeeds, otherwise returns false.
    bool assign(Programmer name, int start, int duration);

      // Cancel all time assignments for the Programmer `name`.
    void cancel(Programmer name);

      // Searches for a vacant time interval of length `duration`,
      // returns the starting time if it finds such an interval,
      // otherwise returns NOT_FOUND.
    int find_interval(int duration);


Task 1. Implement the abstract data type Scheduler.

Implement all public member functions of the class Scheduler. Check the unit tests, make sure that your implementation passes all of them.

Task 2. Write your own unit test.

After your class is ready and passes the tests, come up with a new additional unit test for one of the member functions of the class and write the code for it. Write a short comment about what property your test is checking.