computer science II
c m s c 214  
f a l l   2 0 0 1  

Project 2

Due Tuesday, Oct. 16, 11:59 PM (NEW)

Early Date Sunday, Oct. 14, 11:59 PM (10 points)

Project 2 FAQ

What to do?

If you're done with the two template classes, and need some guidance:

Click here for ideas


The purpose of the Project 2:

  1. To learn how to modify existing code, and test thoroughly, as such changes are being made.
  2. To write a sorted, doubly linked list class as a template class.
  3. To write a unsorted, dynamic array class as a template class. (Basically, you are implementing a version of vector).
  4. To write iterators, nodes as nested classes inside the list class.
  5. To write iterators for the vector class.
  6. To write a template function that sorts the vector class
  7. To write a template function that removes duplicates
  8. To write comments based on CMSC 214 Style Specifications.
  9. To extend the features of the MUD.


A link to a checklist will be provided. You should read the checklist several times, but especially before submitting your project.

Project 2 Checklist

Style Guide

A style guide will be created soon.


We will provide corrections and announcements, as well as "frequently asked questions" on the Project 2 FAQ page.

Project Overview

You will create two kinds of template class: a list class, which will be implemented using a doubly linked list, and a vector class, which will be implemented using a dynamic array.

The program you write will support additional commands and more sophisticated inputs.

As with Project 1, this project will be released in parts. This is the current, expected way to develop your project.

  1. You will be provided Movie.h, Movie.cpp, and MovieSortedList.h.
  2. Implement MovieSortedList.cpp. This is NOT a template class.
  3. You will be provided a minimal SortedList.h, which will be a template class version of MovieSortedList.h, where Movie will be replaced by Data and string (which is the movie's title), will be replaced Key. Both Data and Key are template type parameters.
  4. Implement SortedList.cpp, a template class, by converting MovieSortedList.cpp to a template. (One reason to write a non-template class and convert it, is that it's easier to debug non-template classes).
  5. You will be provided MovieArrayList.h. Implement MovieArrayList.cpp. This is NOT a template class.
  6. You will be provided with a minimal ArrayList.h, a template class. This is similar to a "vector" class in STL.
  7. You will implement ArrayList.cpp, a template class, by converting MovieArrayList.cpp into a template class.
  8. You will be provided a new Parser header files. This will combine four parsers together: DungeonParser, PlayerInputParser, TeamInputParser, and RobotInputParser (if there had been a RobotInputParser, which there wasn't). This will be in a file called Parser.h.
  9. CommandParser will be about the same, except, you should add vector<Robot> (eventually to be changed to ArrayList<Robot>) as a new data member.
  10. Before adding any new commands, you should make sure the original commands still work. Since you will be modifying original code, it's helpful to make those changes one at a time, and test, test, test.

NOTE: It's a good idea to test the SortedList and ArrayList classes thoroughly, before incorporating it into your other classes. Don't implement new commands until the changes have been made. You implement one set of changes first (for example, incorporate SortedList into your code first, then debug, then ArrayList, then debug).

Files Provided

Files That Aren't Needed in Project 2

You shouldn't need the following files:

You will need the code in these files, but they will be reorganized into other classes.

Files You Still Need from Project 1

Files Provided

Files You Write

Background Reading

Background readings will be provided. The main topic will be nested classes.

Nested classes

Read about nested classes here.


Read about operator++/-- lists here.

Useful BNF

This uses extended BNF. See "background readings above".
   <lower> ::== "a" | "b" | "c" | "d" | "e" | "f" | 
                "g" | "h" | "i" | "j" | "k" | 
                "l" | "m" | "n" | "o" | "p" | 
                "q" | "r" | "s" | "t" | "u" | 
                "v" | "w" | "x" | "y" | "z"  
   <upper> ::== "A" | "B" | "C" | "D" | "E" | "F" | 
                "G" | "H" | "I" | "J" | "K" | 
                "L" | "M" | "N" | "O" | "P" | 
                "Q" | "R" | "S" | "T" | "U" | 
                "V" | "W" | "X" | "Y" | "Z"
   <alpha> ::== <lower> | <upper>
   <digit> ::== "0" | "1" | "2" | "3" | "4" |
                "5" | "6" | "7" | "8" | "9" 
   <digits> ::== [ <digit> ]+
   <empty> ::==
   <endl>  ::== "\n"
   <left>  ::== "<"
   <right> ::== ">"
   <tag>   ::== <left> <word> <right>
   <under> ::== "_"
  <blank>  ::== " "
 <blanks>  ::== [ <blank> ]+
<mblanks>  ::== [ <blank> ]+
  <sep>   ::== <blank> | <endl>
 <seps>   ::== [ <blank> ]+
<mseps>   ::== [ <blank> ]*
  <word>  ::== <alpha> [ <alpha> | <digit> | <under> ]*

Input File BNF

The input file looks the same, except there is an additional section for information about robots. See primary input for an example.
   <list_of_robots> ::== <left> "rlist" <right> <seps>
                         [ <onerobot> <seps> ]+
                         <left> "/rlist" <right>
   <onerobot> ::== <left> "robot" <right> <seps>
                         <onename> <seps> <onestrength> <seps>
                         <left> "/robot" <right>
   <listofitems> ::== <left> "itemlist" <right> <seps>
                           ( <empty> | [ <oneitem> [ <seps> <oneitem> ]+ ] )
                           <left> "/itemlist" <right>  
Notice that <listofitems> has been redefined so the list of items may be empty. This definition supercedes the definition in Project 1, which assumed there was at least one item in every room. Use Project 1 BNF for any non-terminals that are not explained here (e.g. <onename>).

Input File Format

See primary input.

Commands/Output File BNF

The list of commands are the same as before, but now they apply to robots. Here are the modification of the commands, as they apply to robots.


  <robotname> ::== <firstname> <blank> <lastname>

Updates of BNF

Whenever the output says to print "MEMBERS", print "PLAYERS" instead.


In this project, you won't use any STL. If you do, you will lose 100 points. The only exception is strings. You can use strings, since they technically part of STL. (Avoid using vectors, algorithms, etc).


  1. The only new assumption is that robots can't join any team.
  2. Of course, just as last time, if there are no relevant error messages, you can assume that the error won't occur. However, this doesn't mean you shouldn't produce error messages of your own (which indicate when something has gone wrong). You should do that for debugging purposes.

Description of Files


These files have been provided to you. Movie is a very simple class. The most important feature of this class (which allows it to be stored in a SortedList class) is the getKey() method. getKey() returns a key, which is used to sort the Movie when it is placed in a SortedList or MovieSortedList object.

Having a getKey() method isn't absolutely necessary (although we use it in Project 2). In fact, in ArrayList and MovieArrayList, you will be sorting using operator< and operator== on Movie objects, just as STL does. As you will notice, Movie does not yet define those operators. You should define those operators in Movie.


This stores a doubly linked list of MovieSortedList::Node objects. Each of these objects contains a Movie object stored by value. You should be able to conver your code for Node, PlayerList, Iterator and ConstIterator and place them into MovieSortedList.

You will notice that Node, ConstIterator, and Iterator are now nested classes, and are not in their own files.

Node nested class

Most of these operators should be familiar to you now, so they won't be explained. However there are a few key changes.

Iterator nested class

There have been bigger changes to the iterator class to make it look closer to the STL iterator classes. Let's look at these changes.

The ConstIterator nested class is similar, except it provides two versions of the operator* operator.

You will also notice it's not necessary to implement copy constructors, assignment operators, nor destructors since the iterator classes do not perform any deep copies.

MovieSortedList main class

Most of the methods are the same as before. However, there are a few new methods. In particular, the methods that return constructors have changed.

Again, it's not quite like the STL iterators (alas!). For example, in an STL iterator, you would be able to create a regular iterator and save it to a const iterator. As set up now, that's not quite possible. This is why there are two versions of the iterators.


A MovieArrayList object attempts to emulate a specific vector. You will templatize this class to create a ArrayList class which is similar to the STL vector (not quite!).

You must observe the following restrictions:

There is no Node nested class for MovieArrayList.

Iterator nested class

curr will hold the address of the current array element. For example, if the iterator is pointing to element 2 of the array list, then curr equals & arr[ 2 ].

You can use pointer arithmetic to move the pointer forward by "n" elements or backward by "n" elements.

The ConstIterator methods are similar to the Iterator methods except fewer methods are offered. For example, there's only const versions of operator* and operator->.

MovieArrayList main class

Special Methods

For each class you write, you must determine whether to write the following methods: Recall that all three methods should be written as a group or not at all. You should use these methods if the class allocates dynamic memory via "new" and deallocates via "delete".

If it is NOT necessary to implement these methods, then do NOT implement. By necessary, this means the class would behave incorrectly (especially, if, say, only the destructor were defined).

If you do choose to write these three methods, you should write the following helper methods.

and use these methods to help implement the default constructor, destructor, operator=, and copy constructor.


The following requirements/restrictions should be observed.
  1. The program should compile with g++ with the -Wall option. You may use cxx to test, but make sure it runs with g++ as well.
  2. You should comment code. You will be given instructions on how to do this later on.
  3. You should use namespaces. In particular, in your .h files (ONLY), all of objects should
  4. You should use namespaces. In particular, in your .cpp files, you should write "using namespace std".
  5. Hardcoded outputs will be severely penalized.
  6. Write helper functions. You will gain more credit if you do. They should be clearly labelled as helper functions.

How to Submit Your Project

As with Project 1
submit p2.tar 2 SUBMIT
You can name the tar whatever you want. However, you should wait until a primary input and output have been posted. (If you submit before that, then if your project does not pass the primary input/output, you will receive a poor grade on the project, most likely a zero).

Academic Integrity Statement

Any evidence of unauthorized use of computer accounts or cooperation on projects will be submitted to the Student Honor Council, which could result in an XF for the course, suspension, or expulsion from the University. Projects are to be written INDIVIDUALLY. For academic honesty purposes, projects are to be considered comparable to a take-home exam. Any cooperation or exchange of ideas which would be prohibited on an exam is prohibited on a project assignment, and WILL BE REPORTED to the Honor Council.


  1. failing to do all or any of the work on a project by yourself, other than assistance from the instructional staff.

  2. using any ideas or any part of another student's project, or copying any other individual's work in any way.

  3. giving any parts or ideas from your project, including test data, to another student.

  4. having programs on an open account or on a PC that other students can access.

  5. transferring any part of a project to or from another student or individual by any means, electronic or otherwise.

  6. publishing any of your code publicly (e.g., via a webpage) which other students can access, even if the project is already due.