Preliminary Material

Project 4 is worth 7% of your grade.

This project enhances and adds to Project 3.

Your doubly linked lists MAY NOT BE CIRCULAR in this project.
You will forfeit all points if we detect circularity.

Your binary search tree Bst must use ModNode which contains a parent pointer.

BstIterator

• Is like a pointer
• It allows one to walk along a binary search tree from one element
  to the next in alphabetical order, beginning at the node containing
  the smallest plaintext string, begin(), and ending at the node with
  the largest plaintext string, end().
• This iterator should be able to walk both forwards and backwards.

Purpose

This project teaches you how to implement an iterator for a binary search tree. It also implements templates, creates base and derived classes, and uses inheritance. The goals of this project are to:

1. Templatize a class that is contained in other classes.
2. Create an inheritance heirarchy for 2 different classes.
3. Understand and implement an iterator for a binary search tree (BST).
4. Recode any functions that were not working correctly in projects 1 through 3.
5. Write and throw exceptions when appropriate.

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 the iterator class BstIterator.h.
  A BstIterator can do an inorder traversal of a BST.
• Use Node as the base class for an inheritance heirarchy.
  ModNode publically inherits Node.
• Use Bst (your old ModBst) as a base class. Bst is pubically
  inherited by Bstplus. Both Bst and ModBst contain ModNodes.
• Make changes to any classes impacted by the above.

In addition, you will include, and add to, myExceptions.h and
myExceptions.cpp

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 primary.input
• This project MUST be successfully submitted in order to pass this course.
• Projects submitted after 2 days late but prior to Dec 8 at
  11PM receive a grade of 10 (out of 100) points.

Tar up your project 3 files or make a copy and store in another directory before you begin this project.

Copy the header files Pair.h, TNode.h, Node.h, Encoder.h, Decoder.h, Decodebook.h, BstIterator.h and DllIterator.h into your account. Some of these have changed.

Create the following header files for which skeletons are provided:

• ModNode.h
• Bst.h
• Bstplus.h

Copy your previous version of myExceptions.h and myExceptions.cpp.

Make any changes to your .h and .cpp files from Project 3.

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. You may not add ANYTHING (including comments) above the comment that tells you to insert your private member functions after it. The only exception to this is when you templatize and inherit, you might have some changes (minimally) but NOT FUNTION NAMES, TYPES OF ARGUMENTS, RETURN TYPES, NUMBER OF ARGUMENTS (except where templatization takes place.)

myExceptions.cpp contains exception classes that are called from several of your .cpp files. You must have at least 15 exception classes:

• the 12 from project 3
• write 2 new exceptions that you determine are necessary
• plus an exception called CodeGarble that is thrown when an unknown 4-digit code needs to be decoded.

Next you should write and/or update unit tests for each of your classes:

• testPair.cpp
• testTNode.cpp
• testNode.cpp
• testModNode.cpp
• testEncoder.cpp
• testDecoder.cpp
• testBst.cpp
• testBstplus.cpp
• testDecodebook.cpp
• testDllIterator.cpp
• testBstIterator.cpp

Remember to keep backups on a different system - perhaps WAM. You can still code on WAM but only the g++ compiler is available there.

And finally you should write a:

main.cpp

It should contain a main function that will call Encoder's reader() method, process the information just read, build the doubly linked list that holds the message, build the dll that holds the codebook (in Encoder) - alphabetically on words/expressions low to high, build the vector holding the decoded message, build the vector that holds the decodebook (in Decoder), print the plaintext message and codebook, and print the code vector and decodebook vector.

Your main program should use the classes created earlier to accomplish it's task. You may *not* write any other classes.

Assumptions

You may assume that

• All words that do not appear in "codebook.txt" are either a garble or are part of an expression
  or the plural of a word in the codebook. Examples of an expression are
  "white flag" and "of course"
• Expressions may be any length but will only have the first or last word missing from codebook
• Expressions will not contain plurals
• There will be no bonus for complicated expressions as in project 3. Unless you are all finished and have extra time, do not put effort into this task.
• Any codes that can be doubled will not have their doubled value in "codebook.txt".
• The word "halt" will never appear in the original message.
• A garble may appear in the coded message that is decoded in Decoder.
• The input will not be empty. Each non-empty line will terminate with a newline.
• There will be neither leading not trailing blanks in the plaintext or coded messages.
• Plaintext messages may contain upper/lower case letters, white space,
  and punctuation, but NO digits.
• Plaintext input is the same as for Project 3
• The input file may be several lines long
• Code input is the same as for Project 3
• The output file may be several lines long

Approach

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

• Task 1
• Review you old code and make certain you have initialized ALL VARIABLES. This is the programmer's responsibility.
• Change Node.h so that it is templatized on Pair. Use template<class T>
• getPair() and setPair() have changed to getWord() and setWord()
• getLeft() and getRight() now return Node *&
• Node now has a destructor
• Rewrite/update testNode.cpp
• Task 2
• Make ModNode publically inherit Node which is templatized.
  Use template<class T>
• ModNode adds one new data member to Node, ModNode * parent
• ModNode should contain only
• constructors
• a default constructor
• a 4 argument constructor
• constructor that takes a pair (or templatized object)
• getParent, an accessor for parent
• setParent a mutator for parent.
• Update testModNode.cpp
• Task 3
• Change Bst to accept its templatized ModNode, still called root.
  It is your old ModBst from Project 3.
• makeEmpty() now takes a ModNode *& argument.
• Bst is not templatized but it contains a templatized object.
  Use template<class T>
• Make certain that search() and locate() take only 2 arguments.
• Update testBst.cpp to reflect these changes.
• Task 4
• Create the class Bstplus which publically inherits Bst.
• Bstplus is not templatized but it contains a templatized object.
  Use template<class T>
• Bstplus contains
• A private data member, BstIterator
• constructors
• a destructor
• operator=()
• begin() which returns a BstIterator pointing to the smallest node in the tree
• end() which returns a BstIterator pointing to the largest node in the tree
• Create testBstplus.cpp and throughly test your class
• Update Encoder.h, Encoder.cpp and testEncoder.cpp to reflect these changes.
  (Encoder now includes Bstplus instead of Bst.
• Task 5
• Create your makefile and test everything together.
• Look at the checklist (link at the top of this web page) to see that you have done all we asked.
• Submit your program and take a big sigh of relief

Clarifications

Hopefully, none are needed. This project does not change the implementation of project 3. It simply adds inheritance.

Sample I/O

You may assume input and output are the same as in project 3.

Your output must diff this time, blank lines and all.

print functions in P4

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.

A secondary input file and a secondary output file are also provided for further testing of your code. However, your project will successfully submit if your program passes the primary.input.

On further secondary inputs, you will be given other plaintext or coded messages in the same format as primary.input   Your program should generate the corresponding output similar to primary.output. Additionally, we will test several portions of 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.

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 4 submissions on 11/16/03.

See the class syllabus for policies concerning email Last Modified: Thursday, October 30, 2003

Web Accessibility