CS246 [Winter 2010] Assignment 5.
DRAFT
V0.1 14 Feb 2010 This is still being actively changed.
V0.2 15 Feb 2010 Fixed typos etc. Added some explanations.
V0.3 16 Feb 2010 Fixed 2 typos.
V0.4 08
Mar 2010 Clarification on linked lists: You are to write your own linked lists
(do not use the C++ STL container).
You are to re-implement the binrel class (from Assignment 4). The new implementation will replace vectors with linked lists. This will also include adding a new constructor (a copy constructor) as well as a destructor. Your progam should, at least in principle, behave just like your program from Assignment 4.
Goals of assignment. This assignment illustrates and gives examples of a number of concepts. It illustrates abstraction --- the binrel class represents a high level concept (binary relations) which can be implemented many different ways. It illustrates use of copy constructors and destructors. It illustrates how a driver (relcalc.cpp) can be largely independent of how its target programs are implemented. It illustrates how a script language can be supported by an interpreter. It gives practice in using C and C++ style pointers with dynamic allocation and how they can replace higher level mechanisms such as C++ vectors.
Replace the implementation of your binrel class. You will develop a new implementation of the same data abstraction (binary relation) but with vectors replaced by linked lists. You are to write your own linked lists (do not use the C++ STL container). You will minimally modify your existing header file binrel.h to include the prototype for the copy constructor and the destructor, now naming the file binrel2.h. You will program a new implementation file binrel2.cpp which will replace the old implementation binrel.cpp. The new executable version of the binary relational calculator should be called relcalc2. The old was simply relcalc.
Ideally, you will only change two files: binrel.h and binrel.cpp (renaming these to binrel2.h and binrel2.cpp as well as changing any #include files that reference them to use the new spelling of these file names). Each file other than binrel.h and binrel.cpp that you modify should include documentation explaining how you changed the file. This should be done as in comments in the file, beginning as follows:
//
How this file was modified.
… more comment lines here …
Use the same main function (perhaps minimally
changed) and the same the same help
function (in help.h and help.cpp) from the last assignment.
Use linked lists In your implementation of the binrel2 class, you are to use linked lists instead of a C++ “vector”. At runtime, generally when a pair is added to (or removed from) a relation, a node is allocated to store the pair and it is linked to the list of pairs representing the relation. For each relation, you are to used a singly linked list of pairs. So, the implementation will generally need to use new and delete statements to create and destroy space for pairs (and their links). Each binrel object will contain a pointer named first which locates the first (if any) pair in the relation. In the case of an empty relation, the first pointer will be NULL, with no allocation of space for pairs. Your implementation should make sure that no space is lost (no memory leakage) and that all pointers are followed only when they actually locate a legitimate data.
Copy constructor and destructor. For your new implementation of the class to work correctly, you need to implement a “copy constructor” as well as a destructor. Note that this constructor is implicitly invoked for value parameter passing of objects. Hint: The Savitch text book gives a detailed example using copy constructors. It also gives examples of overloading operators.
Keep it short. As a rule, in this assignment, shorter, more elegant solutions to this assignment are preferable to more complex and possibly faster running solutions. Do not worry too much about efficiency, but concentrate on correctness.
RSL (Relational Script Language). You can write primitive scripts in RSL as the input language for relcalc and relcalc2. The following is an example RSL program, called example.rsl. RSL has only relations and no real comments or string output. To fake these, a relation called comment is used in the example to act as a comment and a relation called msg is used for writing strings (which cannot contain blanks) encoded as relations.. The first line in the example declares a relation called comment which is never used. The third line declares a relation called empty which is used only to reset the msg comment to null. The msg relation is used only for printing messages encoded as relations. The rest of the script computes and prints relations such as love, like and likeOrLove.
d
comment
i comment
This_is_an_example_script_written_in_RSL .
d
empty
d
msg
i
msg Hello_World!!__Example_with_Bob_Jane_and_friends .
o msg
= msg empty
i
msg love_relation .
o msg
= msg empty
d
love
i love Bob Jane
i love Jane Fred
o love
i
msg like_relation .
o msg
= msg empty
d
like
i like Bob George
i like Bob Jane
o like
i
msg likeOrLove_relation .
o msg
= msg empty
d
likeOrLove
+ likeOrLove like
love
o likeOrLove
i
msg likeButNotLove_relation .
o msg
= msg empty
d
likeButNotLove
- likeButNotLove
like love
o likeButNotLove
i
msg Goodbye_world!!__End_of_script .
o msg
= msg empty
q
When this RSL script is run,
by
./relcalc2 –q
< example.rsl > example.dat
it produces the following output in file example.dat.
Hello_World!!__Example_with_Bob_Jane_and_friends .
love_relation .
Jane Fred
Bob Jane
like_relation .
Bob Jane
Bob George
likeOrLove_relation .
Jane Fred
Bob George
Bob Jane
likeButNotLove_relation .
Bob George
Goodbye_world!!__End_of_script .
Coverage testing. You are to create a test file called cover.rsl that exercises (that causes to execute) all statements in your program (including all files except the help function). The test will consist of input to (commands to) bincalc2. You do not need to exercise cases causes by input that is ill-formed or which produces an error message. These tests should be put into a files called cover.rsl. (RSL is described below.) Put this command in a file called runcover and make that file executable. Execute it by typing ./runcover, and verify that its output is correct.
./relcalc2 -q < cover.rsl >
cover.dat
Note that you tests should produce the same output as the standard course solution for Assignment 3 would produce, except that the order of pairs in a relation may vary. Recall from Assignment 3 that the –q flag causes prompts not to be printed.
Makefile.
Use the same makefile as for the previous assignment (but with the new
spellings binrel2.h, binrel2.cpp and relcalc2).
Related files. You will be given a compiled (master) solution to this assignment. You can run this under a student account to see if your solution gives the same answers. Your output (except when there are user errors) from your program should be the same, character for character, as the master solution. You can get this master solution on your student account using the Unix commands:
curl
http://plg.uwaterloo.ca/~holt/cs/246/2010/asgn05/relcalcdir2/masterrelcalc2
> masterrelcalc
chmod 700 masterrelcalc2
See this URL for files available to you (some in that directory may have been purposely been make non-viewable by you.)
http://plg.uwaterloo.ca/~holt/cs/246/2010/asgn05/relcalcdir2
What to submit. Submit
the following files. No other files or write-ups are needed.
binrel2.h binrel2.cpp relcalc2.cpp help.h help.cpp relcalc2 makefile cover.rsl