Lab 2: A Queue With Intelligence

Overview

Last week you learned about queues and implemented a simple one. However, not all queues in the the real world operate under a first-come first-served rule. For instance, if Tufts is adding maintenance requests to a queue, a new request (say, a broken window at the Campus Center) might have a higher priority than some of the previous entries. Enter the priority queue. This week, you'll still be removing some items from the front of the queue. However, we'll keep them sorted by their priority by inserting them within the queue based on where they belong, not just tacking them all at the end. We'll also remove items from within the queue to simulate a maintenance request that gets removed.

Getting started

Start by copying the files from /comp/15/labs/lab2/ into your home directory (I recommend making a subdirectory called comp15 with another directory inside it called lab2). The files are:

• priorityQueue.h: a header file for the PriorityQueue class. This file serves as the interface, and does not include definitions of the methods. You should not need to modify this file at all.
• priorityQueue.cpp: the implementation of the PriorityQueue class. This file is mostly empty -- your job is to add implementations for the methods in priorityQueue.h
• Node.h: Instead of a struct, we have a Node class today. This class protects the WorkOrder data and manages memory allocation and deletion of WorkOrders. You will not need to edit this file, but you will need to look at it to see how to access a WorkOrder in order to get it's data values.
• Node.o: The object file for the Node class. You only need to know what a Node does, hence Node.h, not how it does it. This file has been tested and compiled and is ready to be linked to your program.
• WorkOrder.h: Instead of last week's simple string variable, WorkOrder is a class that contains and protects two variables (name of the maintenance request and priorityLevel of the request). You will not need to edit this file, but you will need to read it to find out how to ask for the value of its variables.
• WorkOrder.o: The object file for the WorkOrder class. Same thing applies here: you need to know what a WorkOrder does, not how it does it. This is the compiled implementation file ready to be added to your program. See WorkOrder.h to understand how to interact with the class.
• main.cpp: includes a function to test your queue. Feel free to add more tests once you pass those given.

You can copy them all in one command:

cp /comp/15/labs/lab2/* .

Compiling and Running

Edit, Save, and Compile Often!!!

You can use one of two compilers: g++ or clang++. I recommend using clang++ because it gives much better error messages.

clang++ main.cpp priorityQueue.cpp Node.o WorkOrder.o -o mytest
or
g++ -Wall -Wextra main.cpp priorityQueue.cpp Node.o WorkOrder.o -o mytest

To debug your code (especially if you have segmentation faults) you can use gdb (see my quick reference on using the debugger). I also urge you to try running your program using valgrind, a very cool program that checks your program for pointer and allocation problems. Run it like this:

valgrind ./mytest

Providing your Code

As always, you should provide your source code before you leave. The assignment name is lab2.

provide comp15 lab2 priorityQueue.cpp main.cpp