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

Project 1

Due Wednesday, Sept. 26, 11:59 PM

Project 1 FAQ

Preliminary Material

You should read this over. Changes/corrections/additions will be made over the next few days. You may start writing code if you want, but realize you may have to make some changes as the description evolves. You will still probably end up saving time by doing so, then waiting for the description to finalize.

Read the project 1 FAQ (currently empty), to see changes in the description.

Files are located in the "Proj/P1" directory of the posting account. More files will be added later on. Copy these files to a P1 directory in your own account.

Write a makefile, too.

Purpose

The purpose of the Project 1:

  1. To review linked lists, and implement a doubly linked lists, as part of a larger project.
  2. To learn how to use an Standard Template Library (STL) vector.
  3. To learn about C++ style strings.
  4. To partially design classes.
  5. To write comments based on CMSC 214 Style Specifications.

Checklist

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

Style Guide

A style guide will be created soon (within a week). In the meanwhile, comment the code within individual methods.

FAQ

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

Project Overview

This project will be divided into two parts. You will, however, only make one single submission.

Part 1

In the first part of the project, the goal is simply to create a class that contains an STL vector of doubly linked lists. You will implement the doubly linked lists. You will think of each linked list as a list of grades for a particular course. The purpose is to create something simple, yet, similar to the more complicated part of the project.

However, this is only a "warm-up" project.

Part 2

In the next four (possibly five) projects, you will develop a "MUD" (which stands for a "multi-user dungeon"). MUDs are a rather, old version of a networked game. In a typical MUD, you would log onto a game server as a character (which we will call a "player"). This character would carry weapons, treasures, and have attributes like strength, speed, etc.

A common goal is to reach a certain level of a dungeon, where there might be a prize, or perhaps to kill a dragon. In the process, you tried to make your character rich and powerful, at least, more than other characters in the dungeon. Usually, characters would kill mythical beasts, and perhaps other characters in the game.

These games often permitted you to send messages to other people playing the game (thus "multi-user"). Therefore, you could work as a team with other people.

You will write a simple version of a MUD. In this version, there will be Players. A group of players is stored in a PlayerList which represents a team. The list of all teams is in a class AllTeamsList. A PlayerList contains a doubly linked list of Nodes which itself contains a pointer to a Player. Player will be dynamically allocated.

You will define most of the public methods for a Player. We provide you with data members.

The input will be written in something that resembles XML. XML is a markup language, which resembles HTML, except you can invent your own tags. Fortunately, it's rather easy to read XML, so you don't have to learn much to read it, especially, if you can already read HTML.

Files Provided

This project will be divided into two parts. In the first part, you will implement a small version of the "real" project. In the second part, you will implement the "real" project. You must submit files for both parts together.

Part 1

You will be provided the following header files:

These classes are a "simple" version of a doubly linked list class. You will implement methods and a corresponding .cpp file for each.

Part 2

Files To Submit

Part 1

You will need to submit all .h files from Part 1. Furthermore, you will also need to submit

Part 2

Other files

You can provide additional useful information if you choose. It should be name EXACTLY README (not "readme", "Readme", etc). Failure to submit this file may cause you to lose points on the project.

One Big Tar File

You will submit one big tar file for all parts. This will be described in the "How to Submit Your Project" section below.

Background Reading

Abstract Lists

Read about abstract lists here.

C++-style strings

Read about C++-style strings here.

Vectors

Read about STL vectors here.

Iterators

Read about iterators here.

Namespaces

Read about namespaces here.

EBNF

Read about EBNF on the tutorial page 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 

  <start> ::== <dungeon><seps><teamlist><seps><playerlist><seps>
               <commands><mseps>
  <dungeon> ::== <left> "dungeon" <right> <seps>
                 <mseps> [ <room> ]+ <mseps> <seps>
                 <left> "/dungeon" <right> 
  <room>  ::== <left> "room" <right> <seps>
               <onename> <seps>
               <listofitems> <seps>
               <left> "/room" <right>
  <onename> ::==  <left> "name" <right> <seps>
                        <word>
                        <left> "/name" <right> 
  <listofitems> ::== <left> "itemlist" <right> <seps>
                     <oneitem> [ <seps> <oneitem> ]+
                     <left> "/itemlist" <right>
  <oneitem> ::== <left> "item" <right> <seps>
                 <a_name> <seps> <an_id> <seps> <a_weight> <seps> <a_cost>
                 <seps>
                 <left> "/item" <right> <seps>
  <listofteams> ::== <left> "tlist" <right> <seps>
                     [ <team_name> <seps> ]+
                     <left> "/tlist" <right> 
  <team_name> ::== <left> "name" <right> <seps>
                     <word> <seps>
                     <left> "/name" <right> 
  <list_of_players> ::== <left> "plist" <right> <seps>
                               [ <oneplayer> <seps> ]+
                               <left> "/plist" <right>
  <oneplayer> ::== <left> "player" <right> <seps>
                   <onename> <seps> <onestrength> <seps>
                   <onegold> <seps>
                   <left> "/player" <right>
  <onestrength> ::== <left> "strength" <right> <seps>
                     [ <digit> ]+ <seps>
                     <left> "/strength" <right> 
  <onegold> ::== <left> "gold" <right> <seps>
                 [ <digit> ]+ <seps>
                 <left> "/gold" <right> 
  <list_of_cmmds> ::== <left> "cmmdlist" <right> <seps>
                       [ <onecommand> <seps> ] +
                       <left> "/cmmdlist" <right>
  <onecommand> ::== <left> "cmmd" <right> <seps>
                    <cmmd_choice> <seps>
                    <left> "cmmd" <right> 
  <firstname> ::== <word>
  <lastname> ::== <word>
  <personname> ::== <firstname> <seps> <lastname>
  <teamname> ::== <word>
  <roomname> ::== <word>
The entire list of commands for <cmmd_choice> is listed below.

Input File Format

The input file consists of four parts. These four parts A sample input file will be posted in the posting account under sample.input. Use that, along with the BNF, to understand the format of the input.

Commands

You will process the input using input redirection. For example, if your executable is called p1 and you ran it on sample.input, you would type: 
 p1 < sample.input
Of the four parts in the input file, only the last part--the list of commands, causes your program to produce some output.

The following is a list of the commands your program must support. Each of these are one of the choices provided by cmmd_choice. All outputs will be listed in the output BNF.

Output File BNF

Assumptions

You can assume the following.

Description of Files (Part 2)

AllTeamsList.h

CommandParser.h

You must use the private data members provided in the file, and implement the methods shown. In addition, you should write helper methods.

Add any sensible .h files at the top.

Unlike the other parsers, this parser is an object (it's not static). Like the other parsers, it does parse the fourth part of the input file (the list of commands) and runs each command as it processes it.

ConstListIterator.h

DungeonParser.h
DungeonParser.cpp

These files have been provided to you. Use DungeonParser.cpp to help you determine how to parse the other three parts of the input file. Note: these use static functions.

Item.h

Each of these methods should be straight-forward to implement. Two items will be considered "equal" (determined using ==), if they same name and ID. One item, X, will be considered less than another item, Y, (using operator<) if either X's name precedes Y's name lexicographically, or if the two names are the same (using string's ==), then X is less than Y if X's ID is less than Y's ID.

The print() method should do something reasonable for printing output, and should be used by operator<< to print (don't make operator<< a friend of Item).

ListIterator.h

See ConstListIterator.h. The only difference between this class and ConstListIterator is getCurrent(). which returns a reference in ListIterator. Again, you can allow the method to core dump if curr is NULL.

Add const whereever it is appropriate.

Item.h
Item.cpp

These two files have been provided to you. All you have to do is to determine whether to write the copy constructor, destructor, and operator=. You shouldn't have to modify any methods.

Node.h

These methods should be quite similar to IntNode.h. There should be minor modifications.

Player.h

This will probably be the most difficult class (outside of the doubly linked list) to write. This is because the player must maintain a large amount of information. You may define the methods as you see fit. However, you are not permitted to return treasure, as a vector, by value, reference, or pointer. You can return a particular element of the vector if you want (the use may, for instance, specify an index).

You are likely to write many additional public and private methods, and you may also add additional private data members.

PlayerInputParser.h

This parses the third part of the input file, which is the list of players. parse() is a static method. This method will return back a vector of Players. Use DungeonParser.h to guide you on how to write this class.

PlayerList.h

This represents a team. It consists of a team name, a pointer to the first and last node of a doubly linked list of Node's. It also contains the list size, which is the number of nodes in the list. You should not add any dummy nodes to this list, and it should not be circular linked list.

There are the methods it should support.

ReadTag.h
ReadTag.cpp

This file only has the standalone function, readTag. This is used by DungeonParser.cpp and should be used by all other files ending in Parser.

Room.h

This class represents a room. You can add an item and remove an item to the room. This represents the items residing in the room. You must determine reasonable parameters for the remove method. getName() returns the name of the room.

TeamInputParser.h

This parses the second part of the file. It produces a AllTeamsList object as a result. This resulting object is a vector of PlayerList. Recall a PlayerList is a doubly linked list of Players. Again, the parse() method is static.

main.cpp

You must use this main.cpp. This contains main(). You should not need to make any modifications to this file.

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.

Requirements/Restrictions

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.
These requirements and restrictions should be observed for Part 2.
  1. Do not remove data members from classes.
  2. Do not add new data members to classes unless the description says you can.
  3. Implement the PlayerList class using a doubly linked list of Nodes where the first points to the first element of the list and last points to the last element. No two nodes should have the same "key".
  4. For a Player, the key is the player's name.
  5. AllPlayersList should be a vector of PlayerList sorted by the team name.
  6. You may add any private methods you want.
  7. ....more to come.

Which Compiler?

Use g++ -Wall option. You can use cxx as a "backup", but your makefile should include only calls to "g++".

How to Develop Project

  1. Of course, you should write Part 1 first, and create test drivers to convince yourself it works.
  2. Then, write the corresponding classes in Part 2. This should be mostly cut and paste, and reusing the test drivers, but making modifications to handle the new types. At this point, several classes may be less than complete. For example, Player.
  3. Then, read DungeonParser and the sample input. Determine how it works. Write correspoding parsers for the PlayerInputParser and the TeamInputParser.
  4. Work on the CommandParser.
It's expected to take about 5 days to finish Part 1 and 5 more days to finish Part 2. It all depends on how fast you can write doubly linked list code (a reasonably good programmer should be able to do Part 1 in perhaps 2 days---it may still take about 4 days to do Part 2, depending on how you deal with the commands).

How to Test Project

Go to Tutorial page and read about test drivers.

Test Drivers

Go to Tutorial page and read about test drivers.

Makefile

Your makefile should either be called "makefile" or "Makefile". The first target should be "all". It should cause three executables to compile. 
all :  p1  driver1 driver2

p1 :  ...stuff...

driver1 : ...stuff...

driver2 : ...stuff...
p1 must be the name of the executable that runs Part 2. It should not be called a.out or P1 or p1.x or p1.exe. It should simply be p1. If you fail to observe this, you will lose at least 30 points on the project.

driver1 should be your test driver executable for RankingList.cpp. driver2 should be your test driver for AllRankingLists.cpp.

I don't particular care what the drivers do, as long as they reasonably test the the classes mentioned. The goal is to make sure you write test drivers to test your code.

How to Submit Your Project

In order to successfully submit your project, it must pass the primary input and produce the primary output. We will use "diff -bwi" to test your code. This ignores case, treats N blanks as 1 blank, treats N blank lines as 1. We will also strip all blank lines from your input when matching to ours. However, diff is sensitive to punctuation, number of dashes, etc.

If your executable fails to produce an output that matches the primary output, then you will be unable to submit your project. You must then fix your code until it does match.

To submit, run the following command: 

submit p1.tar 1 SUBMIT
where p1.tar can be replaced by whichever tar file you have, and 1 refers to the current project, and SUBMIT refers to a subdirectory that is created by the submit program. You may name this subdirectory any name you want. We use "SUBMIT" as a sample.

This directory should NOT exist prior to running the "submit" command. Either remove the directory and its contents if it does exist, or give it a new name.

If you forget the syntax, simply type "submit", hit return, answer the academic integrity question, and it will tell you the syntax.

Also, if you wish to find out why your project did not submit, go into the temporary directory just created. Look for a file called "214_p1_diff_file". That file will contain the diff between your output and the primary output. It should help you determine what went wrong.

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.

VIOLATIONS OF ACADEMIC HONESTY INCLUDE:

  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.

IT IS THE RESPONSIBILITY, UNDER THE UNIVERSITY HONOR POLICY, OF ANY STUDENT WHO LEARNS OF AN INCIDENT OF ACADEMIC DISHONESTY TO REPORT IT TO THEIR INSTRUCTOR.

Web Accessibility