This homework will focus on the use of templates and iterators in C++.
If you're not familiar with karaoke, here's how it works (for our homework): singers can arrive and leave at any time. All singers have a list of the songs that they like to sing that is maintained at the karaoke lounge. Songs cannot be sung more than once per night (by any singer).
For this assignment, most of the driver code has already been implemented for you. You will be performing two main tasks: 1) converting the type-unsafe LinkedList class into a type-safe template and 2) implementing and using an iterator over the LinkedList data-structure to run the karaoke driver. The current karaoke driver exposes the internals of the LinkedList class to traverse the list. Your version of the code should not leak any details about how the LinkedList is implemented to the user.
To download the code, you can either pull the latest version of the github repository and navigate to the hw6 folder or download each file using wget from hw6files. After downloading the files, you should have access to list.hpp, karaoke.hpp, karaoke.cpp, main.cpp, singers.txt, events.txt, and Makefile. You should be able to immediately build the project using make. You can run the project using:
./karaoke singers.txt events.txt 100
Your first task is to rewrite the LinkedList class to be templated on some type T, rather than storing the data in a void pointer. Your first step toward this goal should be to rewrite the class definitions in list.hpp to remove all void pointers and replace them with templated types. Once you have replaced all 3 classes in list.hpp with templates, you should remove all of the no-longer necessary unsafe type-casts from the code in karaoke.cpp and main.cpp.
Once you have templatized the LinkedList class, your next task is to fill in the LinkedListIterator class defined in list.hpp. You will need to implement at least the following methods:
Once you have implemented a LinkedListIterator, you should rewrite the existing code to remove all uses of LinkedList::getFirst(). The new version of the code should use your LinkedListIterator class, as to not leak the internal implementation of LinkedList to the user code in karaoke.cpp and main.cpp. You can remove the getFirst() method from LinkedList to make it easier to find the code segments that you will need to refactor.
If you need inspiration for how to write an iterator, you can refer to the array_iterator from class.
On some nights, the karaoke director likes to mix things up and reverse the order in which singers will sing every time a new singer enters the club. This functionality can be implemented using the reverse function from the STL's algorithm header file. In order to use this function, you will need to add a few additional methods to your LinkedListIterator to allow it to be a bidirectional iterator instead of a forward iterator. You will also need to provide the typedefs for iterator traits.
The code for this homework has been heavily rewritten from the version used last semester. Therefore, it probably contains bugs! If you are able to find a bug and write a driver that reproduces the bug in the distributed code, you will receive 3 points of extra credit (limit of 3 extra-credit points per student).