Preliminary Material

Project 4 is worth 8% of your grade.

In order to pass this course, you must submit this project. The last possible date for submission is May 5, 2004. See the syllabus for details.

In the previous project, you coded both levels of the game ,EENVG, "Extremely Exciting Non_ Violent Game" (pronounced N-VIG).

What we need to do now is put the finishing touches on the game. These will include using inheritance, changing the data type of the board (from integer to string), and writing an iterator to walk through the BST.

The rules remain unchanged from project 3 (except as indicated above):

• The Robot is represented by the string "R"
• The Stalker is represented by the string "S"
• The points on the board are strings such as "-1", "3", etc. You must convert these to integers to accumulate the Robot's points.
• The Stalker moves AFTER the Robot
• In each round of play, the Robot moves and then the Stalker moves.
• The Robot should always make the "best" move - the cell with the most points that it can reach (based upon Pairs in the BST). The sooner the Robot accumulates enough points and ends the game, the better. If there is more than 1 move with the same number of "most" points, the first move with the "most" points encountered in an inorder traversal of the BST is selected as the Robot's move.
• If the Robot lands upon a cell with negative points, it loses those points. These are stumbling blocks. The positive values on the board are treasures.
• The game is over when
• the Robot's points equal or exceed the value in primary.input.
• the Stalker lands on the Robot (Robot's points will be 0)
• the Robot runs out of moves - there may be moves in the BST but none are reachable from the Robot's current position.
• there are no more positive values that can increase the Robot's points on the board (values greater than 0).
• The game continues if the Stalker runs out of moves. In this case, the Stalker remains on the last cell it moved to before running out of moves.
• After the Robot leaves a cell, the points in that cell are set to 0 (zero)
• After the Stalker leaves a cell, the points in that cell are set to 0 (zero) unless they were negative before the Stalker landed there. In this case, the original negative value is restored to that cell when the Stalker moves on.
• If the Robot accumulates the specified number of points, she begins play on the 2nd board.
• For board 2, the Robot is placed in the same position as her last position on the previous board; if she was at [0,2] when the first game ended, she will be placed in cell [0,2] on the second board (even if the board size changes.)
• the Stalker is placed in the same position as its last position on the previous board; if he was at [1,2] when the first game ended, he will be placed in cell [1,2] on the second board (even if the board size changes.)
• On board2, the Robot's initial points are her previous point count. If she earned 17 points on board1, she begins with 17 points on board2 and adds to this count. If the cell she is placed on does not contain 0 points, her points are adjusted accordingly.
• primary.input contains the number of points the game will be played to for board1 and board2. They are respectively 10 and 20 for purposes of submitting your project.
• The size of board2 may be different from the size of board1. If so, it will be larger.
• The Robot may not land on the Stalker
• The game ends if the BST has moves, but none are reachable from the Robot's current position.

Purpose

This project implements the STL vector class as well as a binary search tree. The goals of this project are to:

1. Understand an inheritance hierarchy and implement code that uses inheritance.
2. Continue to work with templates.
3. Be able to store data in one format (strings) for aesthetic purposes and convert it to another type (integers) for usefulness.
4. Implement an iterator class that can iterator through a BST.

Academic Integrity Statement

Please note that *all* programming projects in this course (including this one) are to be done independently or with the assistance of the instructional staff of this course only.

Please review the policies outlined on the class syllabus concerning the use of class computer accounts and concerning the University's Code of Academic Integrity. The instructors of this course will review the programs submitted by students for potential violations of the Code of Academic Integrity and if it is believed that a violation has occurred it will be referred to the Office of Judicial Programs and the Student Honor Council.

Hardcoding is considered a violation of academic integrity

Style Guide

Students are expected to write "clear and legible" code. Please review the following Style Guide which specifies how students in CMSC 214 are expected to lay out their code:

http://www.cs.umd.edu/class/spring2003/cmsc214/Projects/styleguide.txt

FAQ

Answers to "frequently asked questions" will be posted via the main projects page. Prior to asking a question or submitting a project you should check the FAQ to see if any important information has been covered there. In addition to answers to FAQ's any important information pertaining to a project will be posted on it's FAQ.

E-mailing Questions

DON'T email questions. We cannot keep up with the numerous emails about a project. GO SEE A TA or an instructor during office hours. We will generally NOT respond to email questions about the project.

Project Overview

For this project you will be required, among other things, to write the code for 3 new classes and modify several classes already written:

class 1: BaseRobot

• the base class for Robot and Stalker
• 2 BaseRobot pointers are contained in the Board class
• one points to a Robot
• one points to a Stalker

class 2: BasePair

• the base class for Pair and Mpair

class 3: BstIterator

• the bidirectional iterator that can walk through a BST
• this class is NOT required to pass primary

class 4: Bst

• This class stores the Robot's moves
• This class is templatized on Pair because Node is templatized on Pair.
• You need to add a function begin() to this class that returns a BstIterator.
• You need to add a function end() to this class that returns a BstIterator.
• The binary seach tree stores the Pairs of moves
• The moves for board1 will be in "moves.dat"
• The moves for board2 will be in "moves2.dat"
• The BST will have more moves than are needed.
• Your implementation of erase() must be one of the following:
• easy right pullup
• easy left pullup
• right subtree successor
• left subtree predecessor
• You must implement preorder, inorder and postorder traversals but the printing of the list will use an inorder traversal.

class 5: Robot

• Robot is derived from the base class BaseRobot
• Robot is templatized on Pair (the type in Bst)
• Robot contains Bst<T> move
• Robot no longer contains "position"
• The Robot's moves are contained in a BST
• Robot's initial position on the board is in "robot.dat"

class 6: Stalker

• Is derived from BaseRobot
• Stalker no longer contains "position"
• moves about the board sucking up treasures (+ points)
• it leaves stumbling blocks (- points) unchanged when it moves off of a cell with a negative value
• its moves are stored in a vector
• all moves for the Stalker will be valid moves on the board.
• Stalker's initial position on the board is in "stalker.dat"
• Stalker's moves are in "smoves.dat" (board1) and in "smoves2.dat" (board2)

class 7: Mpair

• is derived from Basepair
• a pair of integers indicating the coordinates of a board cell
• for coordinate [r,c], r indicates the row position and c indicaties the column position
• each row and column begins at 0

class 8: Board

• Board is templatized on the at least 2 (but no more than 4) generic types - these can include int, string, Pair, and Mpair.
• input to the board will be in "board.dat" for board1 and "board2.dat" for board2

class 9: Except

• exceptions that occur in the above classes
• 2 are provided, do not change these
• 3 were written by you for project 1
• 3 were written by you for project 2
• 3 were written by you for project 3
• write 3 other exceptions that could occur in your classes
• you may leave the exceptions (if any) that you wrote for Moves
• you need a total of 14 exceptions
• Note: exceptions must be thrown in the function in which they occur, but they are NOT caught there. They are caught in main or in the function which calls the function containing the exception.

class 10: Node

• Node is templatized on Pair

class 11: Pair

• Is derived from Basepair

In the class posting accounts (~bt214001) you can find the header
files only for the 3 new classes, data files, and main.cpp for the classes. The following rules MUST be adhered to:

• No public functions or (public, protected, or private data members) may be added to the header files.
• Your output must match our output, an example of which is provided in primary.output
• You may not change the input - as provided in primary.input
• Projects submitted after 2 days late but prior to May 5, 2004 at 11PM will receive a grade of 10 out of 100 points.

After copying the header files into your account you should create the corresonding BaseRobot.cpp, Basepair.cpp and BstIterator.cpp and modify the corresponding Pair.cpp, Node.cpp, Bst.cpp, Mpair.cpp, Board.cpp, Except.cpp, Robot.cpp and Stalker.cpp files. You will write the code that implements the member functions for these classes.

Note: you may NOT change the public methods in the header files but may add private methods as needed. You may NOT add private, public or protected data members to any class other than Except.h.

You must add public methods to Except.h only. However, do not change the public methods provided to you. You will add 3 more exceptions to Except.h and Except.cpp.

In each header file you will find the class with it's data member(s) and member function(s). There is a comment before/around each member function describing what it should do. You are to implement (i.e. write the code for) the member functions ABOVE the line

    // YOU MAY PUT ANY PRIVATE METHODS HERE

so that it does what the comment states that it should do and nothing more.

Next you should write 11 unit test files to test each of your classes:

• testBasepair.cpp
• testBaseRobot.cpp
• testBstIterator.cpp
• testBoard.cpp
• testBst.cpp
• testMpair.cpp
• testNode.cpp
• testPair.cpp
• testRobot.cpp
• testStalker.cpp

A unit test file should be a main() for a particular class that calls and tests each public method. It also tests the private methods which are called from public methods. Note that when developing/writing code you should do so in parts/modules and test each as you create it (keeping backup copies!). So for example, when writing Node, you also write a testNode.cpp that is the main() for Node.cpp. It should call all public functions and include appropriate output to test that all Node.cpp code works correctly.

And finally you should test your project with the main provided:

main.cpp

Add your own catch clauses to this file. We will run your main but it must diff down to and including the 2 catch clauses that were written for you for exceptions we provided.

It is expected that your output will match our primary.output exactly

Assumptions

You may assume that

• All input will be read from a file. For example, moves.dat will hold the allowable Robot's moves for board1. It will contain more moves than you will/can use.
moves2.dat will hold the allowable Robot's moves for board2. It will contain more moves than you will/can use. board.dat will hold the dimensions and values for the cells in board1. board2.dat will hold the dimensions and values for the cells in board2. smoves.dat will hold the moves for the Stalker for board1, all of which will be valid moves. smoves2.dat will hold the moves for the Stalker for board2, all of which will be valid moves.
• There may be multiple lines in any file.
• The input will not be empty. Each non-empty line will be followed by a newline (carriage return).
• Your program may be tested using an empty file.
• Each file will contain an EOF marker on the last line.
• "moves.dat" and "moves2.dat" may contain upper/lower case letters and white space, as well as digits.
• all other input files, including primary.input will contain integers only
• for purposes of submitting your program, sizes of boards 1 and 2 will be as specified in "board.dat" and "board2.dat"
• the size of the board may change in subsequent tests for project 4
• the board will always be a perfect square (nXn)

Hints

As soon as the test files are posted for Project 3, go back over project 3 and correct code that failed our tests or was inefficient or incomplete.

Start immediately. You may have some stalls in coding due to inheritance complexities. Although you don't have to implement the iterator class to pass primary, you will lose up to 12 points for failing to do so.

I have left it to you to change your classes, as needed, to get the inheritance parts of the code working. But, you are not permitted to deviate considerably from the methods in project 3. You also may not change implementations or data structures.

Tackle one inheritance problem at a time. Work on getting Mpair and Pair working with Basepair. Then get Robot and Stalker working with BaseRobot.

The BstIterator class is not required for submitting the project. However, you will lose as much as 12 points if you do not get this file working. This should be the last part of the project you complete.

If you work on your class account, tar up your files every day and email them to your wam account. You can always work on the project on the g++ compiler on wam if the detective cluster goes down or is slow.

Sample I/O

You may assume:

• There are no blank lines in the input file.
• Each line terminates with a carriage return.
• The last line contains an EOF marker.

A primary input file and a primary output file are provided in the class posting accounts (in the appropriate directory). You should review these files. They will be named primary.input and primary.output respectively.

Your project will successfully submit if it passes the primary.input.

Your program should generate the corresponding output similar to
primary.output. Additionally, we will test several methods from your code.

When your main program is compiled and run with input redirected so that it gets the contents of the primary input file (primary.input) as input, it should generate output that matches the primary output file. When we test your program we will diff your output (using diff -bwi) with that of the primary output and if it does not match, your program will be considered to not meet the minimum running standards and you will be unable to submit it.

Passing primary does not guarantee a passing grade (70 or above) for your project. Testing your program thoroughly helps.

How to Submit

Provide a makefile that creates an executable file named p4 when the command make p4 is run.

Tar up all necessary files, such as source code, including:

• all .cpp files
• all .h files
• your makefile

submit p4.tar 4

Submit will start accepting project 2 submissions on or about 04/10/04.

See the class syllabus for policies concerning email Last Modified: March 31, 2004

Web Accessibility