CMSC-341 Fall 2002
Project 2
| Assigned |
18 Sept 2002 |
|
| Due |
02 Oct 2002 by 11:59PM |
|
| Updates |
01 Oct 2002
The project description says that the next pointer of
column elements and the down pointer of row elements should be NULL when
they are first created. This is incorrect. These pointers should be set
so that the newly created element points to itself, maintaining circularity
in all lists. |
Background
The List ADT is a fundamental building block for other ADTs such as the
stack and queue. The text describes singly-linked lists and provides an
implementation. In this project you will implement an ADT called a
multilist using the text's code as a starting point.
Iterators provide an abstraction of the concept of position within a data
structure and a mechanism for walking through a data structure one element
at a time. In this project you will implement a bi-directional iterator for
multilists.
This project will require a well thought out design before you can begin
coding. Identifying problems, issues and their solutions at design time
will save you an enormous amount of time compared to finding them at
coding/testing/debugging time. Make sure you understand the text's linked
list and iterator before proceeding. In particular, I think it's very
important to read this entire document carefully.
Description
The text describes multilists and the motivation for them on page 85. I've
copied some of the relevant material here:
"A university with 40,000 students and 2,500 courses needs to be able
to generate two types of reports. The first report lists the registration
for each class, and the second report lists, by student, the classes that
each student is registered for. The obvious implementation might be a
two-dimensional array. Such an array would have 100 million entries. The
average student registers for about three courses, so only 120,000 of these
entries, or roughly 0.1 percent, would actually have meaningful data."
The solution to this problem is a multilist, which uses memory
proportional to the sum of the sizes of the classes. Figure 3.28 in the
text shows a multilist for this problem. NOTE: Your implementation will
be slightly different than the one in the figure. For each class and
each student, there is a circular list, and the elements of these lists are
shared. If a student list and a class list share an element, it means the
student is registered for the class.
In the figure, all nodes but those with Cn (i.e. C1, C2, etc.) and Sn
(i.e. S1, S2, etc.) in them have two pointers. One points to the next node
in the list when moving vertically, and the other points to the next node
in the list when moving horizontally. Each vertical list corresponds to
the classes taken by a student, and each horizontal list corresponds to the
students registered for a class. All of the nodes in your implementation
of multilists will have both types of pointers, including those with Cn and
Sn in them.
In this project you will build a multilist by reading commands from a
command file that specify class names, student names, and which students
are registered for which classes. Once you've constructed the multilist,
further commands will ask you to print the classes for which a specific
student is registered, or the students registered for a specific class.
Here are your tasks:
- Read and understand the singly-linked List and ListItr descriptions
in the text.
- Read and understand the description of multilists on pages 85 and 86
in the text.
- Copy the linked list files (LinkedList.C, LinkedList.H, and
dsexceptions.H) from Dr. Oates' public directory
/afs/umbc.edu/users/o/a/oates/pub/CMSC341
to your directory.
- Modify the linked list code so that the lists are circular.
- Using the linked list implementation as a starting point, implement
the multilist class. See the detailed discussion of what needs to be done
for this task below in the ADT section.
- Design and implement Proj2.C which contains main( ) and is the driver
program for this project.
- Implement a makefile for this project. You can use the makefile
provided for project 1 as a model.
- Answer the questions posed in 341-Fall02-proj2_questions.txt. Copy the
file
/afs/umbc.edu/users/o/a/oates/pub/CMSC341/Proj2/341-Fall02-p2_questions.txt
to your own directory and edit it to provide your answers to the questions.
Don't forget to submit the edited file; it is 10% of this project's grade.
Definition of the ADT
All classes that you design and implement must support the "Big-4", even if
the default behavior provided by the compiler would be acceptable.
- Default constructor
- Destructor
- Copy Constructor
- Assignment Operator
As always, you are free to add whatever private data and methods you
desire, and you must provide the public methods listed in this project
description. Because you are using the List class as the basis for the
Multilist class, you can implement any public methods for the Multilist
class that are also implemented for the List class. If you need to add any
additional public methods, think very carefully about it and provide ample
justification for why the method must be public in comments in your code.
Points will be deducted for public methods that are not well justified.
NOTE: You are not required to implement Multilist analogs of all public
List methods if they are not needed for this project. For example, you
never need to delete nodes from the multilist, so you don't need to
implement a remove() method.
The MultilistNode
Use the ListNode class to create a MultilistNode class. The former has two
private data members - element, which is of type Object, and
next, which is a pointer to a ListNode. The MultilistNode will
have these members, though next will be a pointer to a
MultilistNode, as well as a member named down, which is also a
pointer to a MultilistNode.
Given a MultilistNode, following next pointers moves
horizontally to the right in the multilist (i.e. along one row), whereas
following down pointers moves vertically down in the multilist
(i.e. along one column).
Every node in the multilist will be a MultilistNode. This is in
contrast to figure 3.28 in the text, in which the Cn nodes have no down
pointer and the Sn nodes have no next pointer.
You should implement MultilistNode methods corresponding to all of the
ListNode methods with the following differences:
- The ListNode constructor takes two arguments - an element and a next
pointer. The MultilistNode constructor should take three arguments - an
element, a next pointer, and a down pointer.
The Multilist
Analogously to the List class, the only data member of a Multilist will be
a header that is a pointer to a MultilistNode. The following two methods
operate directly on the header:
- void insertRowElement(const Object & x) -- This method inserts a new
MultilistNode containing x as the first element (i.e. at the head) of the
list pointed to by the next pointer of the header. The next
pointer of the new node will point to the node that used to be at the head
of the list, and its down pointer will be NULL. You will use this
method to insert student names when they are created, e.g. string
name("Jane_Doe"); multilist.insertRowElement(name).
- void insertColumnElement(const Object & x) -- This method inserts a
new MultilistNode containing x as the first element (i.e. at the head) of
the list pointed to by the down pointer of the header. The
down pointer of the new node will point to the node that used to be
at the head of the list, and its next pointer will be NULL. You
will use this method to insert class names when they are created,
e.g. string name("CMSC_341"); multilist.insertColumnElement(name).
Once you've inserted students and classes into the multilist, you will use
the following methods to find them again to, for example, register a
student for a class.
- MultilistItr<Object> zeroth() const -- This method returns an iterator
that points to the header of the multilist. If you follow next
links from the header you'll visit all of the students. If you follow
down links from the header you'll visit all of the classes.
- MultilistItr<Object> findRowElement(const Object & x) const --
This method returns an iterator pointing to the element in the first row of
the multilist containing the given object. You will use this method to find
student names, e.g. string name("jane_doe"); MultilistItr<string> i =
multilist.findRowElement(name).
- MultilistItr<Object> findColumnElement(const Object & x) const --
This method returns an iterator pointing to the element in the first column
of the multilist containing the given object. You will use this method to
find classes, e.g. string name("CMSC_341"); MultilistItr<string> i =
multilist.findColumnElement(name).
Finally, to register a student for a class, you will use the following
method:
- void insertElement(const MultilistItr<Object> & row, const
MultilistItr<Object> &col) -- This method inserts a new node into the
multilist such that the node is shared by the lists pointed to by the row
and col iterators. That is accomplished as follows. First, the new node
is inserted at the head of the list pointed to by the down pointer
of the node indicated by the row iterator, and the down
pointer of the new node is made to point to the node that used to be at the
head of that list. Second, the new node is inserted at the head of the
list pointed to be the next pointer of the node indicated by the
col iterator, and the next pointer of the new node is made to
point to the node that used to be at the head of that list. Note that
you do not pass in a data item to this routine. You will use this
routine to register a student for a class, e.g. string sname("jane_doe"),
cname("CMSC_341"); multilist.insertElement(multilist.findRowElement(sname),
multilist.findColumnElement(cname).
The Iterator
The ListItr class supports only forward iteration via
next links and provides the following public methods
- advance ()
- isPastEnd ( )
- retrieve ()
You must write a
MultilistItr class, based on ListItr, that provides the above methods plus
another public method named down() that moves the iterator vertically
through the multilist by following down links.
The Command Line
Project 2 will be invoked with a command line that consists of a single
argument -- the name of the data file to read. As
usual, you should check the validity of all command line arguments.
The Data File
Commands in the file specify operations to be performed on the multilist.
Each line in the file represents one command. Blank lines may appear
anywhere in the file and should be ignored. Otherwise, you can assume that
any line containing a command is syntactically well-formed. We make this
assumption so you don't have to spend lots of time making the command file
parser bullet proof.
The command file format follows:
- NEWCOURSE <course name> -- Add a new course with the given name to
the multilist (using insertColumnElement). If a course with the same name
already exists, print an error message and continue with the next
command. Names are case sensitive and will not contains spaces..
- NEWSTUDENT <student name> -- Add a new student with the given name
to the multilist (using insertRowElement). If a student with the same name
already exists, print an error message and continue with the next command.
Names are case sensitive and will not contain spaces.
- REGISTER <student name> <course name> -- Register the given
student for the given course (using insertElement). If either the student
or course names are not in the multilist, print an error message and
continue with the next command.
- CLASSLIST <course name> -- Print the names of all students
registered for the given course. If the course does not exist, print an
error message and continue with the next command.
- SCHEDULE <student name> -- Print the names of all courses for which
the given student is registered. If the student name does not exist, print
an error message and continue with the next command.
How will you print, for example, the names of the courses for which a
student is registered? First, you will use findRowElement to find the list
associated with the student's name. Then, you will follow down
pointers. Each node encountered in this manner corresponds to a course for
which the student is registered. To get the name of the course, you must
follow next pointers until you come to the head of the class list, get the
name via retrieve(), and print it out. Then continue to the next course
via down pointers and repeat. The procedure for printing a class
list is analogous.
sample Output
Sample output is available for your study at
/afs/umbc.edu/users/o/a/oates/pub/CMSC341/Proj1/341-Fall02-p1-sample_output.txt
Project Submission
DO submit these files
Because you are submitting your own makefile, you are free to name your
files whatever you like, with the following restrictions:
- All class definitions appear in .H files. Header files may NOT contain
any code.
- All class implementations appear in .C files.
- The name of your executable MUST BE Proj2 (upper-case 'P'). The
submitrun program and the scripts that we use to grade your files assume
that you follow this convention for naming your executable.
DO NOT submit these files
The file dsexceptions.H is provided by the author to provide some minimal
exception classes that are thrown by some of his code. In this project,
it's #included in List.H for the ListItr class. DO NOT submit this file.
This file should be included in your project through your makefile.
Submit Tools
There are a number of tools available to you to check on
your submittal. It is your responsibility to ensure that the submittal is
correct and will result in a successful compilation of your project. Do not
wait till the last minute to submit your files. Give yourself enough time
to check that your submittal is correct.
If you don't submit a project correctly, you will not get credit for
it. Why throw away all that hard work you did to write the project? Check
your submittals. Make sure they work. Do this before the due date.
Documentation for the submit program is on the web at http://www.gl.umbc.edu/submit/.
One of the tools provided by the submit program is submitls. It
lists the names of the files you have submitted.
Additionally, there are two programs for use only by CMSC-341 students
(not part of the UCS submit program). They are in the directory
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/ and are
named submitmake and submitrun. You can use
these programs to make or run your submitted projects.
The syntax is similar to that for submit:
submitmake <class> <project>
Example: submitmake cs341 Proj2
This makes the project, and shows you the report from the make utility.
It cleans up the directory after making the project (removes .o files), but
leaves the executable in place.
submitrun <class> <project> [command-line args]
Example: submitrun cs341 Proj2 test.dat
This runs the project, assuming there is an executable (i.e. submitmake
was run successfully).
Grading and Academic Integrity
Your project will be tested using a variety of command lines, some of which
will be invalid.
Your project will also be tested using a variety of command files which
will test various conditions which your code should handle.
Project grading is described in the Project
Policy handout.
Your answers to 341-Fall02-proj2_questions.txt
are worth 10% of your project grade.
Cheating in any form will not be tolerated. Please re-read the Project
Policy handout for further details on honesty in doing projects for
this course.
Remember, the due date is firm. Submittals made after midnight of the
due date will not be accepted. Do not submit any files after that time.