Project 1: A Customer Service Application - Spring 2024

Due: Tuesday Mar 5, before 9:00 pm

Objectives

  • Practice analyzing a project's requirements.
  • Implementing a circular array.
  • Implementing a circular linked list.
  • Combining two data structures to satisfy a project's requirements.
  • Practice C++ dynamic memory management, i.e. avoiding memory leaks, avoiding double free, protection against wrong accesses in memory (segmentation fault), etc.
  • Practice writing test cases for a project.

Introduction

A large e-commerce company needs to increase the efficiency of their customer service system. Their customer service department works all year around, however, there are some periods with a very high number of requests per day. The current system places the incoming calls in a queue in the order they arrive. Since the number of calls are not sometimes predictable the queue overflows. Once a queue overflow happens the current system creates a larger queue and copies the calls from the older one to the new one. This is a very inefficient process. The Company is looking for a solution that does not overflow and is fast.

You are assigned a task to design and implement a queue which can dynamically expand and shrink and still performs the operations in an efficient manner. This data structure is a combination of circular arrays and a circular linked list. The following figures present an array queue which will become full after two more insertions.

Since the array is full and the calls keep coming in, we create a new array which holds twice as many calls. All new calls will be placed in the new queue. At this point we have two queues, we dequeue from the old array and we enqueue in the new array.

Now, the question is that what if the second queue becomes full too? The solution is creating a third queue and add it to the set of queues. To manage the set of queues we add them to a linked list. To perform the linked list operations efficiently we use a circular linked list. The linked list will change dynamically too since we need to delete the older arrays that become empty.

If we need to allocate a new array queue, we add it as a node after the current cursor and the new node will be the cursor. If we need to deallocate an old array queue, in the linked list we remove the oldest node which is the next node of current cursor. One may notice that the array queues are stored in the linked list in the order they were created.

In this PDF file a sample sequence of operations is provided.

Assignment

Your assignment is to implement a queue data structure which consists of a circular linked list and a series of circular array buffers.

For this project, you are provided with the skeleton .h and .cpp files and a sample driver:

  • fastq.h - Interface for the ArrayBuffer and ListBuffer classes.
  • fastq.cpp - will be completed and submitted.
  • driver.cpp - a sample driver program.
  • driver.txt - sample output from driver.cpp.

Additionally, you are responsible for thoroughly testing your program. Your test program, mytest.cpp, must be submitted along with other files. For grading purposes, your implementation will be tested on input data of varying sizes, including very large data. Your submission will also be checked for memory leaks and memory errors.

Specifications

The ArrayBuffer Class

The ArrayBuffer class has a member variable m_buffer which points to a dynamically created array with the size m_capacity. This class acts as a node in a linked list. It has a member variable m_next which points to the next ArrayBuffer object in the linked list. An ArrayBuffer object is a circular array and represents a queue.

ArrayBuffer::ArrayBuffer(int capacity)
The constructor allocates memory to an array of int type with the size specified by the parameter capacity. If the specified capacity is less than 1, the constructor sets the capacity to 0. For zero capacity the constructor does not allocate memory. The constructor initializes all member variables. The int numbers stored in the array are the ID numbers assigned to the callers.
ArrayBuffer::~ArrayBuffer()
This is the destructor and it deallocates the memory.
void ArrayBuffer::clear()
This function deallocates all memory and reinitializes all member variables. This function can be used by other functions such as destructor or overloaded assignment operator.
ArrayBuffer::ArrayBuffer(const ArrayBuffer & rhs)
Copy constructor, creates a deep copy of rhs. A deep copy has its own memory allocated. Note: there is no need to initialize m_next to a value in this class, since this pointer is managed by the linked list class ListBuffer.
const ArrayBuffer & ArrayBuffer::operator=(const ArrayBuffer & rhs)
The overloded assignment operator, creates a deep copy of rhs. It needs to deallocate the current memory if any, and reallocate new memory to create a deep copy. It also needs protection against self-assignment. Note: there is no need to initialize m_next to a value in this class, since this pointer is managed by the linked list class ListBuffer.
void ArrayBuffer::enqueue(int data)
This function inserts the data into the array buffer at the proper index. The proper index is the end of the list indicated by the member variable m_end. After every insertion, the function updates the appropriate member variables in the object such as m_end and m_count. If the array is already full, the function throws the exception overflow_error. The exception is defined in the include library <stdexcept>.
int ArrayBuffer::dequeue()
This function removes a piece of data from the start of the list in the array. The start index is indicated by the member variable m_start. After removal, the function updates the appropriate member variables in the object such as m_start and m_count. The dequeue function returns the data value. If the buffer is empty the function throws the exception underflow_error. The exception is defined in the include library <stdexcept>.
bool ArrayBuffer::empty() const
This function returns true if the array buffer is empty otherwise it returns false.
void ArrayBuffer::dump()
This function prints out the contents of an array queue to the standard output. Note: The implementation for this function is provided to you. The purpose of this function is to facilitate debugging.

The ListBuffer Class

The class ListBuffer has a pointer to an object of type ArrayBuffer. The pointer is stored in the member variable m_cursor. The ListBuffer is a circular singly linked list. The first node of the linked list has a buffer with the size indicated by the member variable m_minBufCapacity. This value is passed through the constructor. The enqueue function inserts data into this buffer. Once the buffer is full, the enqueue function inserts a new node (ArrayBuffer object) into the linked list and starts to insert data in the new buffer. The size of the new buffer is a factor of the size of the buffer in the previous node. We use the constant global variable INCREASE_FACTOR to define the size of the new buffer. For example, if the size of the buffer is 100, and it becomes full, we create a new buffer with the size (INCREASE_FACTOR x 100).

To limit the size of buffer arrays we use the constant global variable MAX_FACTOR. For example, if the minimum size of buffer is 100, the maximum size of a buffer cannot exceed (MAX_FACTOR x 100). As soon as we reach to the maximum size, the next buffer will be created with the minimum size which is defined by the variable member m_minBufCapacity.

To remove data from the queue, the dequeue function removes the data from the start index in the oldest buffer (ArrayBuffer object) of the linked list. If a buffer becomes empty, the dequeue function removes the buffer from the linked list. If there is only one node in the linked list and its buffer is empty, we do not remove the node. Always there is at least one node in the linked list.

For the ListBuffer class, you must implement the following methods in the file fastq.cpp:

ListBuffer::ListBuffer(int minBufCapacity)
Constructor creates a ListBuffer object which contains the first buffer (ArrayBuffer object) of this object with the size minBufCapacity. If minBufCapacity is less than 1, the constructor creates a buffer with default size DEFAULT_MIN_CAPACITY. The constructor also initializes the member variables of the class.
ListBuffer::~ListBuffer()
The destructor deallocates all memory in the object. Every ListBuffer object has pointers to ArrayBuffer objects, then we also need to deallocate memory for the ArrayBuffer objects. To clean an ArrayBuffer object we can call clear() function from ArrayBuffer.
ListBuffer::clear()
This function deallocates all memory in the object. Every ListBuffer object has pointers to ArrayBuffer objects, then we also need to deallocate memory for the ArrayBuffer objects. To clean an ArrayBuffer object we can call clear() function from ArrayBuffer.
void ListBuffer::enqueue(const int& data)
This function inserts data into the queue. It adds the data item at the end index of the newest buffer in the linked list. The newest buffer in the linked list is represented by the member variable m_cursor. We can call ArrayBuffer::enqueue(int data) to insert the data item. If the buffer has space, the insertion is performed correctly. If the buffer is full, ArrayBuffer::enqueue(int data) throws the overflow_error exception. The exception should be caught here. If an exception is caught, we need to insert a new buffer in the linked list and insert the data item into the new buffer. The new buffer is inserted as the next node of the cursor. Then we advance the cursor, i.e. the new buffer becomes the cursor of the circular linked list.
int ListBuffer::dequeue()
This function removes data from the queue. It removes the data item from the start index of the oldest buffer in the linked list. The oldest buffer in the linked list is represented by the next node of the member variable m_cursor. We can call ArrayBuffer::dequeue() to remove. If the buffer is not empty, the removal is performed correctly. If the buffer is empty, ArrayBuffer::dequeue() throws the underflow_error exception. The exception should be caught here. If an exception is caught, we need to remove the node containing the empty buffer from the linked list and remove data from the next node. If there is only one node remaining in the linked list and it is empty, this function throws the underflow_error exception which can be caught by the user program.
In a nutshell, if the dequeue operation is successful, this function returns the data item, otherwise it throws the underflow_error exception.
ListBuffer::ListBuffer(const ListBuffer & rhs)
Copy constructor, creates a deep copy of rhs. We can use the copy constructor from ArrayBuffer class here to create deep copies of ArrayBuffer objects.
const ListBuffer & ListBuffer::operator=(const ListBuffer & rhs)
The assignment operator, creates a deep copy of rhs. We can use the copy constructor from ArrayBuffer class here to create deep copies of ArrayBuffer objects.
void ListBuffer::dump()
This function prints out the contents of all array queues in the linked list to the standard output. Note: The implementation for this function is provided to you. The purpose of this function is to facilitate debugging.

Additional Requirements

  • The class declarations (ArrayBuffer, ListBuffer) and provided function implementations in fastq.cpp may not be modified in any way. No additional libraries may be used.
  • You are not allowed to use STL template containers in the ArrayBuffer and ListBuffer classes.
  • You are allowed to use STL template containers in your test functions.
  • The class functions must be written in fastq.cpp; in particular, they must not be written “in-line.”
  • Private helper functions may be added, but must be declared in the private section of the ArrayBuffer and ListBuffer classes. There is a comment indicating where private helper fuction declarations should be written.

Testing

  • The test file name must be mytest.cpp; the file name must be in lower case, a file name like myTest.cpp is not acceptable.
  • The test file must contain the declaration and implementation of your Tester class and the main() function as well as all your test cases, i.e. calls to your test functions.
  • You are responsible for adequately testing your work before submission. The following section presents a non-exhaustive list of tests to perform on your implementation.
  • You must write a separate function for every test case.
  • Every test function must return true/false depending on passing or failing the test. Visual outputs are not accepted as test results.
  • The dump() function should not be called in the test functions. The dump() function is only provided to facilitate debugging.
  • Tests cannot be interactive. The test file mytest.cpp must compile and run to completion.
  • An example of declaring, implementing, and calling a test function, and outputting the test results was provided in the driver.cpp file of project 0.
  • The testing guidelines page provides information that helps you to write more effective test cases.

Note: Testing incrementally makes finding bugs easier. Once you finish a function and it is testable, make sure it is working correctly.

Testing ArrayBuffer Class

  • Test ArrayBuffer class for inserting and removing data items for normal cases. (Note: We need to test the queue functionality. To test the queue functionality, enqueue and dequeue functions would be tested together. We fill the queue with a certain number of data, and we check whether we can remove the same sequence of data without a problem.)
  • Test ArrayBuffer class for inserting and removing data items for edge cases. (Note: We test the queue functionality with edge sizes for data, i.e. inserting and removing one data item, inserting and removing data with the same size as the buffer size.)
  • Test ArrayBuffer class for inserting and removing data items for exception cases. (Note: We test the dequeue operation on an empty queue, and the enqueue operation on a full queue.)
  • Test ArrayBuffer class copy constructor for normal and edge cases. We need to check whether a deep copy is created. There are two ways of doing this. We can compare the array pointers, they should not match. Then, We compare all values in the corresponding cells, all values should match. Another way of checking on deep copy is to clear the rhs object, and check whether the current object contains data by calling dequeue function. Either way is acceptable.

Testing ListBuffer Class

  • Test ListBuffer class for inserting and removing data items for normal cases. (Note: We need to test the queue functionality. To test the queue functionality, enqueue and dequeue functions would be tested together. We fill the queue with a certain number of data, and we check whether we can remove the same sequence of data without a problem. To perform this test the data size would be much larger than the data size used to test the same functionality in the ArrayBuffer class. We want to make sure that ListBuffer adds more ArrayBuffer objects as required. The example of data size in this test would be 10,000.)
  • Test ListBuffer class for removing data items for exception cases. (Note: We test the dequeue operation on an empty queue. Trying to remove from empty queue throws an underflow_error exception. The ListBuffer class never gets full, then it never throws an overflow_error exception.)
  • Test ListBuffer class copy constructor for normal and edge cases. (Note: We can call the test function for ArrayBuffer class copy constructor here.)
  • Test ListBuffer class assignment operator. To check whether it created a deep copy, we can clear the rhs object and check that the data is preserved in the current object by calling dequeue.

Testing For Memory Leaks / Memory Errors

  • Run your test program in valgrind; check that there are no memory leaks or errors.
    Note: If valgrind finds memory errors, compile your code with the -g option to enable debugging support and then re-run valgrind with the -s and --track-origins=yes options. valgrind will show you the line numbers where the errors are detected and can usually tell you which line is causing the error.
  • Never ignore warnings. They are a major source of errors in a program.

What to Submit

You must submit the following files to the proj1 submit directory:

  • fastq.h
  • fastq.cpp
  • mytest.cpp (Note: This file contains the declaration and implementation of your Tester class as well as all your test cases.)

If you followed the instructions in the Project Submission page to set up your directories, you can submit your code using the following command: 

   cp fastq.h fastq.cpp mytest.cpp ~/cs341proj/proj1/

Grading Rubric

The following presents a course rubric. It shows how a submitted project might lose points.

  • Conforming to coding standards make about 10% of the grade.
  • Your test program is worth 50%. If you submit the sample driver program as your test program or no test program is submitted there will be 50% deduction.
  • Correctness and completeness of your test cases (mytest.cpp) make about 15% of the grade.
  • We have written test cases to test your submission without knowing anything about your code. Therefore, it is extremely important that your submission conforms to the specified requirements. Passing tests make about 30% of the grade.
  • There is a 5% deduction for every modification that we need to perform to compile and run your work. For example, if we need to rename your file from myTest.cpp to mytest.cpp the deduction will be applied.

If the submitted project is in a state that receives the deduction for all above items, it will be graded for efforts. The grade will depend on the required efforts to complete such a work.