Background A basic version of the program that includes a skeleton Rolodex class is provided. The class has methods for rotating the Rolodex forwards and backwards, for returning the value of the card at the current position, and for inserting a new card either before or after the current card. The initial version of the program implements the basic sorting algorithm, which is a modified version of insertion sort (it is consequently not very efficient). In addition, it supports a command line processing mechanism that allows you to run the program with options. The initial version recognises two options: -v (verbose) and -c (current). The verbose option causes the actions of the Rolodex to be reported as they occur, which might be useful when debugging, whilst the current option causes the program to print only the current cards value rather than all card values.

Since you do not know how many entries the Rolodex will hold, you will need to use dynamically allocated memory to store the information. An easy way to implement the Rolodex file is using a doubly linked list. Each item in the list will store the information for a single card and will need an instance variable to store the card value as well as pointers to the next and previous items. For example, you could represent the items like this:

struct RolodexItem {

std::string value_;

RolodexItem* next_;

RolodexItem* prev_;

};

You will also need some way of knowing when you have reached the beginning or end of the Rolodex. One strategy is to use a circular list with a sentinel value that marks both the beginning and the end. This approach will considerably simplify the management of the links when items are inserted or removed.

Level 3: Deletion Modify the program such that an input string that begins with a - causes that word (without the -) to be deleted from the Rolodex instead of inserted. For example, if the input is the quick black fox jumps -black brown over the lazy dog then the output would contain the word brown but not black. Deleting a word should be implemented by moving the Rolodex to the position where the word would normally be inserted, but then deleting the current item if it matches the word (if it does not match, no action is performed). You will need to add a method to the Rolodex class that deletes the current item and leaves the Rolodex positioned so that the current item is the one following the deleted item if there is a following item, or the item preceding the deleted item otherwise.