-
Preliminary Material
-
Project 2 is worth 9% of your grade.
This project enhances and adds to Project 1.
Your doubly linked lists MAY NOT BE
CIRCULAR in this project.
You will forfeit all points if we
detect circularity.
iterator
- is like a pointer
- it allows one to walk along a
data structure from one element
to the next, regardless of the
implementation of the underlying data structure.
-
Purpose
-
This project teaches you how to implement an iterator for a doubly
linked list. It also enhances the features of the Encoder and uses a
templatized class.
The goals of this project are to:
- Understand and implement an iterator for a doubly linked
list.
- Templatize a class that is contained in other classes.
- Locate expressions that consist of more than one word.
- Write and throw exceptions when appropriate.
- Enhance the output for readability.
-
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 DllIterator.h
- templatize MNode
- make changes to the Encoder and Decoder classes
- use AI (artificial intelligence) to construct
expressions
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
- Projects submitted after 2 days late will receive a grade of 0
points.
Tar up your project one files or
make a copy and store on another computer, disk or account before you begin
this project.
Copy the header files Pair.h,
MNode.h, Encoder.h, Codebook.h, Node.h,
Decoder.h, myExceptions.h,
Decodebook.h and DllIterator.h
into your account. Some of these have changed.
Copy myExceptions.cpp
Make any changes to your .h and .cpp files from Project 1.
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.
myExceptions.cpp contains exception classes that are called
from several of your .cpp files. You must have at least 9 exception
classes:
- 2 were written for you
- 4 you wrote for project 1
- write 3 new exceptions that you determine are necessary
Next you should write and/or update unit tests for each of
your classes:
- testPair.cpp
- testNode.cpp
- testEncoder.cpp
- testDecoder.cpp
- testTNode.cpp
- testCodebook.cpp
- testDecodebook.cpp
- testDllIterator.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
- There will be no garbles in the input plaintext or code.
- All words that do not appear in "codebook.txt" are part of an
expression
or the plural of a word in the codebook. Examples of an
expression are
"united states" and "of course"
- "united" might not be in codebook but "united states" will be
- "course" might not be in codebook but "of course" will be
- Do not assume there will be only 2
words in an expression.
- 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.
- 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 1
- the input file may be several lines long
- code input is the same as for Project 1
- the output file may be several lines long
-
Approach
-
You might want to take a 6-pronged approach to this project:
- Task 1
- Change makePlural() in Pair.h, Pair.cpp and
Encoder.cpp (the argument was removed)
- Task 2
- Make the changes to Encoder.h and Encoder.cpp
- In depunc() replace ! or . or ? with the word "halt".
- Add the operator[] method.
- Add the copy() method for the copy constructor.
- Make the changes to checkCodebook(). It must now implement
both 1 and 2.
- Update testEncoder.cpp
- Task 3
- Create DllIterator.cpp to walk through an object of type
Encoder.
- Write testDllIterator.cpp
- Write begin() and end() (which return DllIterators) in
Encoder.cpp
- Update testEncoder.cpp to reflect these changes.
- Task 4
- Change decode() to replace "halt" with a period in
Decoder.cpp.
- Task 5
- Templatize MNode.h and MNode.cpp.
- Rename them TNode.h and TNode.cpp
- Make changes to any other classes that are dependent upon
TNode -
anything that formerly used MNode.
- It is strongly suggested that you
make a copy of all your working files
and put them in a separate
directory in case things go badly and you
destroy working
code.
- Task 6
- Add the method erase() to Codebook.cpp.
- Update testCodebook.cpp to reflect this change.
-
Clarifications
-
reader() from Encoder
- reads a line of input
- appends it to message
insert() from Encoder
- puts each individual word in the plaintext message into the
dll wordlist
- message should have already been decaped and depunced
- this does not call decap() or depund() or reader()
insert() from Codebook
- inserts IN ORDER based upon the English plaintext
- You may NOT use a sort to
accomplish this. Your insert() should
locate the correct
position for the new word and place it there.
checkCodebook()
- dll for plaintext message has already been created with
insert()
- reads codebook.txt, establishing the Codebook dll
- checks each node in plaintext dll to see if word is
in the Codebook dll; if not it checks for plurals and multiple
words
- "fixes" the plaintext dll
- if "united" is in one node and the next node contains
"states",
but only "united" and "united states" appear in the
Codebook dll,
then your code detects that these 2 nodes must
be
combined
into one node (i.e. delete one node after combining the words
and
placing them together in a single node.)
- if a node containing "what" is followed by a node
containing "a"
followed by a node containing "day", but only "what a
day"
appears in the codebook dll, those 3 words must be combined
and placed into ONE node, deleting the other two.
- is called after insert() in main.cpp
decap() and depunc() are called from main.cpp.
-
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.
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 p2
when the command make p2 is run.
Tar up all necessary files, such as source code, including:
- all .cpp files
- all .h files
- your makefile
submit p2.tar 2
Submit will start accepting project 2
submissions on 10/12/03.
