Please read the remarks about programming problems for this course.

---

A multilist is a linked structure that allows data to be sorted in more than one way. For example, a set of records containing an identification number (an int), a name (a C++ string object), and an age (an int) may be stored simultaneously in numerical order by ID, lexicographical order by name, and numerical order by age. The data is not duplicated; pointers are responsible for imposing an ordering of the data. Your task is to implement such a 3-way, doubly-linked list.

The following figure shows a typical node within a multilist sorted by ID numbers, names, and ages:

The next figure shows a multilist containing four nodes.

The first pointer points to a sentinel node at the beginning of the list. It is not a real data node, it serves only to mark the beginning of the list. The real nodes begin after this head sentinel node. The last pointer similarly marks a non-data node at the end of the list. Sentinel nodes require only a very small amount of space (relative to the space required for a typical multilist), but their use makes the coding of node insertion and removal much easier.

Notice in the figure that if you follow the red solid pointer from outside this collection of nodes into the Dino node and then visit each node in order following the red solid links, the names will appear alphabetically. Similarly, if you trace the black dashed pointers from outside this set through all the nodes in this set, you will visit the nodes in order from oldest to youngest.

Fortunately the code to implement a multilist is not as messy as the picture showing the links of the pointers! When you add a new node to the multilist you must adjust the pointers so as to preserve the six possible traversal sequences. You have experience inserting an element into a one-way doubly-linked list, so here you essentially must do three insertions for each node added.

Given the Multilist interface multilist.h and sample client code testmultilist.cpp, provide the multilist implementation (multilist.cpp) that completes the program. The comments within multilist.h provide more details about how you should implement the methods. You may not change multilist.h. Your multilist.cpp file must compile with my multilist.h file.

A name will contain only alphabetic characters, and not contain spaces. The input of names may contain a mixture of capitalized and uncapitalized letters within the names, but you should store the names in all upper-case letters. The printing methods traverse the multilist in the appropriate way, printing each record as follows:

• Each record (name, ID number, age) is printed on its own line
• The 3-tuple is printed within parentheses, name first, then ID number, followed by age, each with a comma in between but without any spaces; for example, the following sequence of commands

  + 145 Fred 34 + 200 Wilma 33 + 420 Dino 3 + 85 Barney 25 + 300 Betty 27 + 50 Pebbles 2

  issued to the testmultilist.cpp program would insert this information into multilist. The user then can traverse the list in various ways:

  n Printing by name (BARNEY,85,25) (BETTY,300,27) (DINO,420,3) (FRED,145,34) (PEBBLES,50,2) (WILMA,200,33) N Printing by name reverse (WILMA,200,33) (PEBBLES,50,2) (FRED,145,34) (DINO,420,3) (BETTY,300,27) (BARNEY,85,25) i Printing by ID number (PEBBLES,50,2) (BARNEY,85,25) (FRED,145,34) (WILMA,200,33) (BETTY,300,27) (DINO,420,3) I Printing by ID number reverse (DINO,420,3) (BETTY,300,27) (WILMA,200,33) (FRED,145,34) (BARNEY,85,25) (PEBBLES,50,2) a Printing youngest to oldest (PEBBLES,50,2) (DINO,420,3) (BARNEY,85,25) (BETTY,300,27) (WILMA,200,33) (FRED,145,34) A Printing oldest to youngest (FRED,145,34) (WILMA,200,33) (BETTY,300,27) (BARNEY,85,25) (DINO,420,3) (PEBBLES,50,2)

Note that the multilist.h header file contains the declaration of the Node constructor but not its definition. You must define the Node constructor in your multilist.cpp file. The Node class is nested privately within Multilist class. This nesting makes the syntax for the definition a little interesting; the following shows the proper syntax:

If you leave off the Multilist:: prefix, the compiler will interpret this as a definition of a constructor for a non-nested globally visible Node class, which, of course, is not declared anywhere.

When you are finished submit your multilist.cpp file to eclass.e.southern.edu.