The University of British Columbia

CICS 216
Assignment #2

The Busy Russel

Objectives:

Implementation of Vectors Using Different Data Structures.

Concepts:

Fixed-Lenght Arrays.
Dynamic Arrays.
Structures.
(Dynamic) Arrays of Structures.
Linked Lists.

Fortunately, Russel could find a job in a company as a software developer. He is happy with his job, which involves writing efficient algorithms for a list of problems which he receives every Monday from his boss. There are some easy problems, and some which require more effort, and may be left over for the next week. Russel feels that if he can keep track of his job list, he can have a better performance.

Tasks:

The purpose of this assignment is to make you familiar with the concepts of dynamic data of the C++ language. The data type (linked list) you will develop in this assignment is used as the base data structure for further assignments. Therefore it is important that you don't fall behind in this assignment, otherwise you may need to work more in the later assignments to catch up.

Suppose that the each problem given to Russel has a unique ID (of type int), a description (of type string), and a deadline (of type Date: see Assignment#1). Russel wants to store these information for later access. He needs to be able to add/remove jobs from his job list. We will use 4 different data structures for this purpose, and will explore their advantages and limitations.
Fixed-Length Arrays
Arrays of Structures
Dynamic Arrays
linked lists

Fixed-Length Arrays:

The simplest way to store the job list is to define 3 sufficiently large arrays,
int jobID[MAX_JOB_NUM];
string jobDescription[MAX_JOB_NUM];
Date jobDeadline[MAX_JOB_NUM];
where MAX_JOB_NUM is the capacity of arrays defined as, e.g.
#define MAX_JOB_NUM 100
at the beginning of the source code. Adding/Removing a job to/from the end of arrays is easy and efficient, e.g.
jobID[++totalJobs] = newJobId; for adding, and --totalJobs; for removing, where totalJobs indicates the number of jobs already in the array.
Howevever, there are three major drawbacks here:

1. We have defined 3 different arrays, despite the fact that the values stored in them are dependent. It is easy to confuse a particular jobId with another job's description, if add and remove are not performed correctly.
2. The capacity is fixed. Nothing can be done if suddenly, Russel goes to a short vacation, and needs to store MAX_JOB_NUM+1 jobs!
3. The amount of effort (complexity) needed to remove a job from the middle of the array is high.
   (Optional: Try to implement a void remove(int fromWhere) function. You can easily see that its average complexity is 1/2*MAX_JOB_NUM for a full array).

Arrays of Structures:

To tackle problem 1, we use a C struct Job with three elements: ID, Description, and Deadline. Note that we don't use a class here, because our purpose is just to link these three elements, and not to define any functions for manipulating them. Then we can have a single array:
Job jobList[MAX_JOB_NUM];
Please implement the add and remove fuctions to/from the end of jobList .

Dynamic Arrays:

To remove the second limitation of fixed-length arrays, we need to use a dynamic array to store the items. Such an array is declared as a pointer, and its space is allocated later by the class member functions. Usually, the class keeps two constant values: the initial size of the array and the increment factor. The constructor initializes the array with space equal to the initial size. The add operation checks the available space before it adds any element in the vector. If the array is full, it expands it by the increment factor. In your case, you should set the initial size to 5 and the increment factor to 0.2 (i.e. 20%). In addition, the class needs to keep track of the capacity of the array and the actual size of the vector, in order to determine when expansion is required. Please implement a class DynamicJobList for this purpose, and define appropriate add/remove functions (to/from the top). Also overload the [] operator, as discussed in the appendix at the end of this page. You can see that we still have a high complexity if we want to remove from the middle of the array (optional: implement it!).

linked lists:

The linked list keeps a cursor (pointer) that points to the beginning of the vector. We then can begin from this cursor, and advance to the next item and access its value. This way, the user can access all the vector values in the order in which they are stored in the vector. The linked list data structure significantly reduces the complexity of adding/removing to/from arbitrary locations, Because the pointers can be assigned to the new values in the vector (see Unit#3 course notes (Page 17) for more details). It also has dynamic capacity (why?).

To implement the LinkedJobList class, first modify the struct Job to contain appropriate next pointers.
It is extremely important to always set these next pointers to point to appropriate Job (or NULL) during the implementation of all functions in the LinkedJobList class. Then define in the class
i) the cursor which points to the beginning of the linked list (i.e., Job *cursor ), and
ii) int length to indicate the number of elements in the vector.
Recall that you can iterate on a linked list by using somthing like:
for (Job* j=cursor; j!=NULL; j=j->next) { ... }
Our LinkedJobList class should provide the following operations:

• LinkedJobList()
  An initializer that constructs an empty linked list: It sets the cursor to NULL , and sets length to 0.
• int size( )
  Returns the vector's length.
• void push( Job *j )
  Adds the job to the end of the linked list. ( Don't forget to set j's next to NULL !)
• Job* start()
  Returns the pointer to the first value in the vector.
• Job* end()
  Returns the pointer to the last value in the vector.
• Job* pop()
  Removes the last job from the linked list, and returns a pointer to it.
• void insert(Job *j, int toWhere)
  Inserts j before the toWhere 'th element of the linked list. Note that insert(j,0) is a valid operation (insert at the beginning). However, insert(j,m) where m > length-1 is not valid. (In this case, the function does nothing).
• Job *j remove( int fromWhere)
  Removes the fromWhere 'th element and return a pointer to it. Note that if fromWhere > length-1 , then nothing is removed and NULL should be returned.
• Job operator[](int i)
  Returns the i'th element in the list (see the appendix ). If i is out of range (i<0 or i>length-1), then a default INVALID_JOB must be returned. (For example INVALID_JOB can be defined with the ID of 0, Description of "INVALID", and Deadline of 1/1/1800.)
• void print()
  Prints all the vector values in the following format:
  job1_ID[TAB]job1_Deadline[TAB]job1_Description[END_LINE]
  job2_ID[TAB]job2_Deadline[TAB]job2_Description[END_LINE]
  ...
  jobN_ID[TAB]jobN_Deadline[TAB]jobN_Description[END_LINE]
  (where N is the length, and [TAB], and [END_LINE] indicate a '\t', and '\n', respectively.)
  In the special case where the list is empty, the following message should be printed:
  [TAB][TAB][TAB][TAB][TAB]Hurrah![TAB]No more jobs for this week![TAB][TAB][TAB][TAB][TAB]
  
• ~LinkedJobList()
  Last but not least, the destructor, which is in charge of deleting all elements in the list. (HINT: Use delete remove(i) for i from length-1 to 0. (Can you explain why we need to delete backwards?) )

Appendix: Overloading the [] operator

To allow the user to use the the indexing operator []  to access the i-th value of a dynamic array, you need to overload  the [] operator in the DynamicJobList, LinkedJobList classes. Define the operator  in such a way that a call  to v[i] will return the i-th value stored in the vector v. The acceptable indices are the integers from 0 to length-1. If the index is outside these bounds the program should print an  error  message and terminate the execution. Note that the operator call v[i] does not allow the user to change the  i-th location in the vector; it just returns the value.

In summary, you should do the following:

• Provide struct Job, and use it to implement add, remove functions for fixed-length and dynamic arrays.
• Define the LinkedJobList class which is able to push, insert, pop and remove correctly.
• Overload [] operator for both DynamicJobList and LinkedJobList classes.
• Write a test driver and test the class.
• The test should clearly show that each method works properly.
  For the LinkedJobList class, you neeed to test all the special cases, e.g. i) inserting to / removeing from the beginning, ii) pushing into an empty list, and iii) poping from a list with one element. Most of the bugs happen when a pointer is not set to the next element or is not reset to NULL.
  You should annotate  the output indicating the methods being tested by each part of it.

Further Readings:

Learn to use VC++ Debugger and Locate the Runtime Errors.
C++ STL Vector Class.
C++ STL List Class (Uses Doubly Linked Lists for Enhanced add/remove Efficiency).