Preliminary Material

Project 1 is worth 8% of your grade.

This project (and the 3 following it) deals with a robot moving about a chess-like board and picking up points or losing points depending upon what is in the cell it lands upon. The allowable "moves" of the robot will be stored in a circular doubly linked list of Pairs. Each pair consists of the direction of the move and the number of squares (positions) moved. The iterator class used in Project 0 will be adapted for this project to work on a circular dll. "Dit" becomes random access iterator. You will be coding the set-up of the project at this time. Other parts (like the Robot) will be added in later projects.

There will also be another pair, Mpair, that stores the row and column on the playing board. This allows you to insert and change the contents of the cells on the board.

• move - a pair that supplies the direction, as well as the number
  of squares on the board, which a robot can move.
• board - like a chess board but implemented as a vector of vectors
  of integers. Its coordinates are Mpairs like [1,2] (the cell in row 1 column 2).
• random access iterator - a pointer-like object that accesses the
  elements in a vector. It can move both forwards and backwards. It also
  allows for random access into the circular doubly linked list.

Purpose

This project implements the STL vector class as well as a circular doubly linked list. The goals of this project are to:

1. Understand a circular doubly linked list.
2. Review and implement the C++ string class.
3. Understand the STL vector class and manipulate a vector.
4. Understand and implement a random access iterator class.
5. Understand and write exceptions for each class.

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

Points may be deducted for not following the style guide.

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 7 classes:

class 1: Pair

• 1st element: one of 8 possible directions: N, NE, E, SE, S, SW, W, NW
• 2nd element: an integer indicating the number of squares to be moved on the board

class 2: Node

• the building blocks of the Moves class
• its elements are Pairs

class 3: Moves

• circular, doubly linked list containing Nodes of Pairs
• is ordered on direction first and then on number of squares to be moved
• input for the list will be in "moves.dat"

   Circular doubly linked list front after inserting one node into the list:

   Circular doubly linked list after inserting 3 nodes:

   Circular doubly linked list showing iterators:

class 4: Dit

• a random access iterator that moves about the dll. It has the capability of ++ and --, iterator math such as it+3 and allows random access of Nodes
• begin() returns an iterator pointing to the first node in the dll
• end() returns an iterator pointing to the last node in the dll unlike a real iterator; our ranges [it, it+3] will include all node between "it" and "it+3", including "it" and "it.end()"
• neither begin() nor end() are valid if the cdll is empty

class 5: Mpair

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

class 6: Board

• the playing board - consists of a vector of vectors
• adapted from your text's "d_matrix.h" on page 264
• input to the board will be in "board.dat"

      Board::Board(int r, int c, const int& init) :
         rows(r), cols(c),
         matrix(r, vector<int>(c, init))
      { }

      vector<int> & Board::operator[](int i) {
         if (i < 0 || i > rows)
          throw IndexRangeError("invalid row index, ", i);
        else
        return matrix[i];
      }

class 7: Except

• exceptions that occur in the above classes
• 2 are provided, do not change these
• write 3 other exceptions that could occur in your classes using the same format as that of those provided
• 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.

In the class posting accounts (~bt214001) you can find the header
files 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 "moves.dat" and "board.dat"
• Projects submitted after 2 days late will receive a grade of zero.

After copying the header files into your account you should create the corresponding Pair.cpp, Node.cpp, Moves.cpp, Mpair.cpp, Board.cpp, Except.cpp and Dit.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 function so that it does what the comment states that it should do and nothing more.

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

• testPair.cpp
• testNode.cpp
• testMoves.cpp
• testMpair.cpp
• testBoard.cpp
• testDit.cpp - different from that in P0

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

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

Approach

You might wish to take the following approach to this project:

• Code Pair first. This is the object contained in your Node class. Test it thoroughly.



• Code the Node class next. You can adapt the Node you wrote in P0 to this Node. Test thoroughly.



• Write Moves next. This holds your circular doubly linked list. Temporarily leave out any iterator methods. Test throughly. When you find a good place for an exception, code it or make a note to yourself to return and code it later.



• Code the Mpair class. You will need this for the Board. Test throughly.



• Code the Board class. It contains Mpairs. You should be able to lift the code from the text and adapt it. Put exceptions in as you go, or make note to return and code them later. Test throughly.



• Code the Dit class. This is the least important class for passing primary. However, it is still worth some points. You can adapt much of your code from Iterator in P0.



• If you haven't added your exceptions, do that last.

Assumptions

You may assume that

• All input for the robot will be read from the file moves.dat
• All input for the board will be read from the file board.dat
• There may be multiple lines in the file.
• The input will not be empty. Each non-empty line will be followed by a newline (carriage return).
• Each input file will contain only an EOF marker on the last line.
• Input may contain upper/lower case letters and white space, as well as digits.

Hints

In order to adapt the iterator class to successfully work on our circular, doubly linked list, we must work with end(). In a circular dll, both begin() and end() would then be pointing to the same node "front". So let's do the following. Allow the range to go up to and include the last node in the range. Then the picture would indicate that if we processed this dll from begin() to end(), we will process ALL nodes.

There is NO DUMMY NODE in this dll. So when we ask for a range of dll.begin() to dll.end(), the iterator can move from the 1st node in the dll to the last node.

Iterator arguments indicate a range [x,y] where both x and y are included in the range. So, for example, if you were operating on a range erase(dll.begin(),dll.begin()) the result would be the erasure of 1 node. After operating on erase(dll.begin(),dll.end()), the entire dll would be emptied.

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.

The input files are provided and will not be redirected input. You may hardcode "moves.dat" and "board.dat" when reading input. A primary output file is provided in the class posting accounts (in the appropriate directory). You should review these files. The output for submission is named primary.output.

Your project will successfully submit if it diffs with our primary.output.

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 our input files so that it gets the contents of the "moves.dat" and "board.dat" 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 should be unable to submit it.

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

String Help

If you need review on the String Class a few good web sites are:

• Strings 0
• Strings 1
• Strings 2
• Strings 3

How to Submit

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

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

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

submit p1.tar 1

Submit will start accepting project 1 submissions on or about 02/17/04.

See the class syllabus for policies concerning email Last Modified: February 16, 2004

Web Accessibility