Program for Operate the Rolodex
Rolodex is a rotating file, usually used to record business contact information. Cards are inserted in alphabetic order by name. You operate the Rolodex by rolling it forwards or backwards until you find the information you need (or find the place where a new card should be added). Your task is to create a data structure that could be used to simulate a Rolodex and use it to implement a simple sorting algorithm named rolosort. Rolosort is a variation on insertion sort. You start with an empty rolodex, then add items one by one in the appropriate positions to maintain overall sorted order. However, rather than searching from the beginning of the list to find where a new item belongs, rolosort searches either backwards or forwards from the location of the previously inserted item. Nevertheless, like insertion sort rolosort has complexity O(n2). In other words, it's not very efficient. Your program should read words from standard input and add them to the rolodex at the appropriate position. When all input has been processed, it should move the rolodex to the beginning and then output each word in order, one per line. A suitable structure for the input processing part of the program is as follows:
string word;
Rolodex r;
while (cin >> word) {
if (r.atBeginning() || r.currentValue() <= word) {
while (!r.atEnd() && r.currentValue() < word) {
r.rotateForward();
}
r.insertBeforeCurrent(word);
} else if (r.atEnd() || r.currentValue() >= word) {
while (!r.atBeginning() && r.currentValue() > word) {
r.rotateBackward();
}
r.insertAfterCurrent(word);
}
}
Background
Define a class named Rolodex to represent the data structure. The class will need methods for rotating the file forwards and backwards, for returning the value at the current position, and for inserting a new value either before or after the current position.
class Rolodex {
public:
bool atBeginning();
bool atEnd();
void rotateForward();
void rotateBackward();
const string& currentValue();
void insertAfterCurrent(const string&);
void insertBeforeCurrent(const string&);
private:
...
};
Since you don't 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 need a place to store the value (a string), and pointers
to the next and previous items. For example, you could represent the items like this:
stuct RolodexItem {
string value_;
RolodexItem* next_;
RolodexItem* prev_;
};
Finally, you'll need some way to know when you've reached the beginning or end of the file. 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.
Core Function Points
1. Complete a main program and enough of the implementation of the Rolodex class so that the program compiles without errors (the methods need not do anything useful at this stage!)
2. Complete the implementation of Rolodex so that all the methods work correctly. The insert methods should leave the Rolodex positioned so that the current item is the one just inserted.
3. Modify the main program so that if run with the command line argument -d (meaning "avoid duplicates") it inserts a new item only if the item is not already present in the file. For example, if the input consisted of the text
far far away
then the output would contain only two lines
away
far
4. Modify the main program so that if run with the command-line argument -r ("report") it outputs a report of the rolodex operations rather than the words themselves. The report should consist of 3 integer values separated by spaces: the number of items inserted, the number of times the rotateForward operation was performed, and the number of times the rotateBackward operation was performed. For example, if the input consisted of the text
the quick brown fox jumps
over the lazy dog
then the output should read
9 5 8
The report indicates that there were 9 words inserted, which required 5 forward rotations and 8 backward rotations of the rolodex.
5. Modify the program so that if run with the option -a ("alphabetic"), uppercase and lowercase letters are considered equal for the purposes of comparison (as they are in a dictionary). Thus if the input is
dog ant
Cat BEE
the output should have ant before BEE if the comparison is alphabetic (because A comes before B in the alphabet), but BEE before ant otherwise (because capital letters come before lower case letters in the ASCII table).
Here's the difference in the expected output for the data above in the "alphabetic" and "default" (ASCII) cases:
6. Make sure the program works correctly if more than one option is specified, where options can be specified in combination and any order. Note that specifying both -d and -a implies that if a word appears twice but with different case, the output will list the version that occurs first in the input. For example if the input was
Bee ant BEE ANT
Then the output will contain ant and Bee
You'll find it easier to implement flexible option argument processing if you use the getopt function (you'll need to #include ).
Extension Function Points
7. Make your Rolodex class generic, with the type of the rolodex entry a parameter to the template. Thus your rolodex object should be declared as
Rolodex r;
Because a template is not compiled until it is instantiated, both the definition and the implementation of a template class need to go in the class header file (and there is thus no need for a class implementation file).
8. Make sure your code works for large input data sets (it will be tested with input that contains tens of thousands of words). The simplest way to test your program with a large data set is to redirect its standard input to come from a data input file, and send its output to a result file. Then you can examine the output file with a text editor to make sure it is correct.
rolosort < in.txt > out.txt
You can use any text file as the source of data for testing purposes. You can find out how many words are in a file with the wc Unix command
wc -w filename
9. Extend your program so that if a file name is specified as a command-line argument, then the program reads its input from that file instead of from standard input. If the input file does not exist (or is not accessible), then the program should report an error message on standard error
(cerr).
$ rolosort -da xxx
Can't read xxx
10. Extend the program so that if the command line contains more than one file name, each will be processed in turn. For example, if three file names are specified
$ rolosort -rda xxx yyy zzz
then the output will contain three sets of results (in this case, 3 reports):
12 17 19 <- report for file xxx
59 232 236 <- report for file yyy
79 336 367 <- report for file zzz
Note that because the sort for each file is independent, you will need separate Rolodex objects for each file. Since each file could be large, and since there could be many files to process, you will need to make sure that your Rolodex class has a destructor that deletes all of the items it has created; otherwise, your program is likely to run out of memory.
Programming Style Points
11. Layout. The code uses indentation and white space to clearly display organisation and function. Layout rules are applied universally and consistently.
12. Names. Names clearly indicate the purpose and function of the entity they name, and are of suitable length for their roles. Where appropriate, names follow naming conventions.
13. Structure. Control structures are well matched to the tasks they perform. Variables are declared only when necessary, and have appropriate scopes and types.
14. Documentation. All external interfaces are documented according to accepted conventions. Internal documentation is used where necessary and adds value to the code.
Assessment
Pairing
You are encouraged to work on this assignment in pairs. If you work as a pair, you must both hand in a solution (which should be identical). All work handed in will be checked using a similarity checker; if more that 2 solutions appear similar, marks will be withheld pending investigation.
Automatic assessment
The function points for this task will be assessed automatically using the demo and try programs under the task name rolosort. You can run the demo version using demo rolosort and you can test your work using try rolosort <>. If the source code consists of more than one file, you'll need to submit your work as a zip file.
The assignment will be assessed twice: once following the "core" hand-in date, and again following the "extension" hand-in date. The "core" submission will be given a score out of 10, based on the 6 core function points and the 4 style points. The "extension" submission will also be given a score out of 10, based on all 10 function points, and deducting marks for poor style.
You can redeem the "core" score (but not the "extension" score) by taking the optional end-of-semester exam. The better of the "core" score and the pro-rated exam score counts towards your final assessment.